This work discusses the problem of sparse signal recovery when there is correlation among the values of non-zero entries. We examine intra-vector correlation in the context of the block sparse model and inter-vector correlation in the context of the multiple measurement vector model, as well as their combination. Algor…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,042 papers · 148 categories
Trend · papers per month
48 results for “Sparse Vector”
Sparse JL with higher sparsity improves feature hashing accuracy.
problem Efficiently reducing high-dimensional feature vectors to lower dimensions.
method Sparse Johnson-Lindenstrauss transform with varying sparsity levels.
result Sparse JL with sparsity greater than 1 provides better norm preservation.
Is it possible to find the sparsest vector (direction) in a generic subspace with ? This problem can be considered a homogeneous variant of the sparse recovery problem, and finds connections to sparse dictionary learning, sparse PCA, and many other …
Study on recovering supports of multiple sparse vectors from mixed linear measurements.
problem Recovering supports of multiple sparse vectors from a mixture of linear measurements.
method Developed algorithms to identify the support of all component vectors using polynomial and quasi-polynomial number of measurements.
result Polynomial and quasi-polynomial number of measurements sufficient for recovering the supports of all component vectors.
Study improves error bounds for sparse regression with heavy-tailed covariates.
problem Estimating sparse coefficients in linear regression with heavy-tailed covariates.
method Employed an -penalized Huber regression method.
result Error bound identical to Gaussian case for -subexponential covariates.
Screening is an effective technique for speeding up the training process of a sparse learning model by removing the features that are guaranteed to be inactive the process. In this paper, we present a efficient screening technique for sparse support vector machine based on variational inequality. The technique is both …
In this paper, we investigate the recovery of a sparse weight vector (parameters vector) from a set of noisy linear combinations. However, only partial information about the matrix representing the linear combinations is available. Assuming a low-rank structure for the matrix, one natural solution would be to first app…
We create interpretable word embeddings through sparse coding.
problem Difficult to interpret word embeddings in natural language processing.
method Transform pretrained dense word embeddings into sparse embeddings through sparse coding.
result Sparse embeddings are more interpretable and achieve good performance.
Sparse support vector machine (SVM) is a popular classification technique that can simultaneously learn a small set of the most interpretable features and identify the support vectors. It has achieved great successes in many real-world applications. However, for large-scale problems involving a huge number of samples a…
SOLAR improves search efficiency and accuracy with sparse, orthogonal embeddings.
problem Bottleneck of indexing large dense vectors and NNS for query efficiency and accuracy.
method Proposes SOLAR embeddings: sparse, orthogonal, learned, and random vectors across multiple GPUs.
result Successfully trains 500K dimensional SOLAR embeddings for 1.6M books and multi-label classification.
Paper reviews advances in solving sparsest vector problem in subspaces.
problem Finding the sparsest vector in a low-dimensional subspace.
method Geometric analysis of optimization landscapes and efficient nonconvex optimization algorithms.
result Recent advances in global nonconvex optimization for sparsest vector problem.
msPCA solves sparse PCA for multiple components efficiently.
problem Sparse principal component analysis with multiple components.
method Alternating maximization algorithm for sparse loading vectors, with orthogonality or zero correlation constraints.
result Achieves high variance explained with sparse components and controlled feasibility violations.
We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fr…
This paper proposes a new algorithm for multiple sparse regression in high dimensions, where the task is to estimate the support and values of several (typically related) sparse vectors from a few noisy linear measurements. Our algorithm is a "forward-backward" greedy procedure that -- uniquely -- operates on two disti…
Paper proposes efficient inner product approximation for hybrid sparse and dense vectors.
problem Efficient search in hybrid spaces with both sparse and dense components is challenging.
method Proposes a technique to approximate inner product computation in hybrid vectors.
result Achieves over 10x speedup and higher accuracy in search compared to baselines.
Sparse group Lasso optimizes sparse and grouped parameters in high-dimensional data.
problem Simultaneously sparse and grouped parameters in high-dimensional linear regression.
method Sparse group Lasso, debiased sparse group Lasso, statistical inference.
result Matching upper and lower bounds on sample complexity and estimation error.
New method improves robust sparse association estimation.
problem Outliers in high-dimensional data.
method Splitting robust estimation into optimization phases, using augmented Lagrangian and adaptive gradient descent.
result Improved precision over existing methods.
Sparse PCA selects variables with FDR control for improved performance.
problem Sparse PCA selects irrelevant variables when maximizing explained variance.
method Proposes FDR-controlled selection using T-Rex selector.
result Significant performance improvement over traditional sparse PCA.
Stochastic gradient descent (SGD) is commonly used for optimization in large-scale machine learning problems. Langford et al. (2009) introduce a sparse online learning method to induce sparsity via truncated gradient. With high-dimensional sparse data, however, the method suffers from slow convergence and high variance…
Using a Bayesian approach, we consider the problem of recovering sparse signals under additive sparse and dense noise. Typically, sparse noise models outliers, impulse bursts or data loss. To handle sparse noise, existing methods simultaneously estimate the sparse signal of interest and the sparse noise of no interest.…
DFSOS improves sparse discriminant analysis for high-dimensional data.
problem Sparse discriminant analysis in high-dimensional settings with feature selection.
method Deflation-Free Sparse Optimal Scoring (DFSOS) using Bregman iteration and orthogonality-constrained optimization.
result DFSOS achieves comparable or better classification accuracy than deflation-based methods.
Sparse neural encoding can store more memories as targets become sparser.
problem Storing sparse input-target associations in neural networks.
method Mathematical proofs using properties of random polytopes and sub-gaussian random vector variables.
result The capacity of neural maps increases with sparsity in target layers.
In compressed sensing, in order to recover a sparse or nearly sparse vector from possibly noisy measurements, the most popular approach is -norm minimization. Upper bounds for the - norm of the error between the true and estimated vectors are given in [1] and reviewed in [2], while bounds for the $\ell_…
Dynamic sparseness reduces neural network computation by selectively omitting parts of computations.
problem Reducing the computational and memory footprint of neural networks.
method Combining dynamic sparseness with block-wise matrix-vector multiplications to selectively omit parts of computations.
result The proposed method outperforms static sparseness and achieves similar perplexities at half the computational cost.
Sparse Polynomial Chaos expansions improve accuracy and efficiency in simulations.
problem Challenges in computational efficiency and accuracy for Polynomial Chaos modeling.
method Sparse Bayesian learning using Variational Relevance Vector Machines.
result Sparse Polynomial Chaos expansions achieve comparable performance to compressive sensing with fewer data points.
In this paper, we generalize Huber's criterion to multichannel sparse recovery problem of complex-valued measurements where the objective is to find good recovery of jointly sparse unknown signal vectors from the given multiple measurement vectors which are different linear combinations of the same known elementary vec…
Study on recovering sparse linear classifiers from mixed binary responses.
problem Learning a mixture of sparse linear classifiers from binary responses.
method Query-based approach to identify all sparse vectors from a set.
result Upper bounds on the number of queries required for recovery.
We consider a decomposition method for compressive streaming data in the context of online compressive Robust Principle Component Analysis (RPCA). The proposed decomposition solves an - cluster-weighted minimization to decompose a sequence of frames (or vectors), into sparse and low-rank components, from com…
Quantum Sparse Codingquant-ph
Quantum algorithm improves sparse vector recovery from noisy measurements.
problem Accurately recover sparse vectors from noisy linear measurements.
method Formulated as a QUBO task, solved using quantum technology.
result Quantum approach outperforms classical methods in sparse coding.
Transfer learning improves sparse, interpretable probabilistic classification.
problem Sparse and interpretable models in transfer learning.
method Two transfer learning extensions integrated into sparse and interpretable probabilistic classification vector machine.
result Transfer learning extensions improve sparsity and performance.
This letter proposes a sparse diffusion steepest-descent algorithm for one bit compressed sensing in wireless sensor networks. The approach exploits the diffusion strategy from distributed learning in the one bit compressed sensing framework. To estimate a common sparse vector cooperatively from only the sign of measur…
Enhances sparse coding for motion data classification.
problem Efficiently decompose motion data into sparse combinations.
method Combines DTW and kernelized sparse coding with non-negative constraints.
result Effective in motion capture data interpretation and discrimination.
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxationcs.LG
Paper solves NP-hard sparse mixed linear regression problem with provable guarantees.
problem Sparse mixed linear regression on unlabeled data.
method Invex relaxation for intractable problem with theoretical guarantees.
result Exact recovery of data labels and close approximation of regression parameters.
Sparse linear regression with compressed and low-precision data via concave quadratic programmingmath.OC
New method recovers sparse vectors from compressed, noisy data.
problem Recovering sparse vectors from compressed and noisy measurements.
method Non-convex quadratic programming exploiting prior magnitude information.
result More efficient support recovery with sufficient conditions for success.
We study the problem of inferring a sparse vector from random linear combinations of its components. We propose the Accelerated Orthogonal Least-Squares (AOLS) algorithm that improves performance of the well-known Orthogonal Least-Squares (OLS) algorithm while requiring significantly lower computational costs. While OL…
New method estimates sparse canonical vectors efficiently.
problem Sparse canonical vectors estimation in CCA.
method Quasi-Bayesian estimation via Rayleigh quotient function.
result Achieves minimax rate with low computational cost.
Paper develops a decoder for sparse codes without encoder matrix, achieving optimal recovery.
problem Designing a decoder for sparse codes from linear measurements alone.
method Matrix factorization to recover encoder and sparse coding matrices from measurements.
result Decoder-Expander Based Factorisation recovers encoder and sparse coding matrix at optimal measurement rate with high probability.
We consider the high-dimensional sparse linear regression problem of accurately estimating a sparse vector using a small number of linear measurements that are contaminated by noise. It is well known that the standard cadre of computationally tractable sparse regression algorithms---such as the Lasso, Orthogonal Matchi…
Paper reveals free information from differential privacy mechanisms improving query accuracy.
problem Improving query accuracy with differential privacy mechanisms.
method Analysis of Noisy Max and Sparse Vector mechanisms.
result Noisy Max releases the noisy gap between the approximate maximizer and runner-up.
Random sinusoidal features are a popular approach for speeding up kernel-based inference in large datasets. Prior to the inference stage, the approach suggests performing dimensionality reduction by first multiplying each data vector by a random Gaussian matrix, and then computing an element-wise sinusoid. Theoretical …
Bayesian Lasso Sparse model provides sparse estimates in linear and nonlinear regression.
problem Sparse learning in regression models.
method Develops a new sparse learning model using type-II maximum likelihood procedure.
result The BLS model provides sparse estimates and is more precise, especially with noisy data.
Paper addresses robust sparse vector mean estimation under local differential privacy.
problem Challenges in defending poisoning attacks on multi-item users in LDP protocols.
method Randomized Projection with Clipping (RPC) to handle clipping bias and enhance robustness.
result Proposes a method that achieves comparable or better performance than existing methods under trusted environments and significantly enhances robustness under untrusted environments.
Data-aware methods for dimensionality reduction and matrix decomposition aim to find low-dimensional structure in a collection of data. Classical approaches discover such structure by learning a basis that can efficiently express the collection. Recently, "self expression", the idea of using a small subset of data vect…
New algorithms recover sparse tensor principal components efficiently.
problem Recovering sparse tensor principal components from noisy data.
method Family of algorithms interpolating between polynomial-time and exhaustive search, tailored for sparse and highly sparse regimes.
result Our algorithms recover sparse vectors for signal-to-noise ratios beyond previous limits, with time complexity .
Paper improves learning mixtures of sparse signals from noisy measurements.
problem Learning mixtures of sparse linear regressions from noisy measurements.
method Improves upon state-of-the-art results using sparse polynomials and error-correcting codes.
result First robust reconstruction algorithm for mixtures of more than two sparse signals.
Paper develops IFTRR to solve sparse generalized eigenvalue problems efficiently.
problem Finding the leading eigenvector with at most k nonzero entries in sparse generalized eigenvalue problems.
method Inverse-free truncated Rayleigh-Ritz method (IFTRR) with a new truncation strategy.
result IFTRR efficiently finds the support set of the leading eigenvector for large scale problems.
SKI accelerates GP inference with sparse grids to handle higher dimensions.
problem SKI scales poorly in high dimensions due to dense grid size.
method Sparse grids within SKI framework, novel matrix-vector multiplication algorithm.
result SKI can be scaled to higher dimensions while maintaining accuracy.
New method sets explicit sparsity for groups of vectors in deep learning and NMF.
problem Tackles the challenge of achieving a desired average sparsity level in vector groups.
method Designs a new sparse projection method that sets the sparsity level for the whole set explicitly and automatically tunes the sparsity of each vector.
result Shows significant improvements in accuracy and reconstruction errors compared to existing methods in deep learning and NMF.