A note on sparse least-squares regression

DOI10.1016/J.IPL.2013.11.011MaRDI QIDQ2446076zbMATH OpenOpenAlexFDO

Authors Christos Boutsidis, Malik Magdon-Ismail

Publication date 15 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.7499

zbMATH Keywords

algorithmsleast squaresregressionregularizationsparse approximationsparsificationtruncated SVD

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Ridge regression; shrinkage estimators (Lasso) (62J07)

Abstract: We compute a emph{sparse} solution to the classical least-squares problem $mi{n}_x||Ax-b||,$ where $A$ is an arbitrary matrix. We describe a novel algorithm for this sparse least-squares problem. The algorithm operates as follows: first, it selects columns from $A$, and then solves a least-squares problem only with the selected columns. The column selection algorithm that we use is known to perform well for the well studied column subset selection problem. The contribution of this article is to show that it gives favorable results for sparse least-squares as well. Specifically, we prove that the solution vector obtained by our algorithm is close to the solution vector obtained via what is known as the "SVD-truncated regularization approach".

Recommendations

• Approximate sparse linear regression
• Sparse regression: scalable algorithms and empirical performance
• A note on rank reduction in sparse multivariate regression
• Sparse linear regression from perturbed data
• Sparse regression using mixed norms
• SPARSE AND ROBUST LINEAR REGRESSION: AN OPTIMIZATION ALGORITHM AND ITS STATISTICAL PROPERTIES
• Regularity properties for sparse regression
• Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
• A sparsity preserving stochastic gradient methods for sparse regression
• Sparse Partial Least Squares Regression for Simultaneous Dimension Reduction and Variable Selection

Cites work

• Algorithms for simultaneous sparse approximation. I: Greedy pursuit
• Algorithms for simultaneous sparse approximation. II: Convex relaxation
• An improved approximation algorithm for the column subset selection problem
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Greed is Good: Algorithmic Results for Sparse Approximation
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Near Optimal Column-Based Matrix Reconstruction
• Some Applications of the Rank Revealing QR Factorization
• Sparse Approximate Solutions to Linear Systems
• The truncated SVD as a method for regularization
• Tikhonov Regularization and Total Least Squares

Cited in

(11)

• Optimal column subset selection for image classification by genetic algorithms
• Regularity properties for sparse regression
• Linear Regression With a Sparse Parameter Vector
• Sparse matrix transform based weight updating in partial least squares regression
• Recovering PCA and sparse PCA via hybrid-(_1,_2) sparse sampling of data elements
• Non-negative sparse regression and column subset selection with \(L_1\) error
• SPARSE AND ROBUST LINEAR REGRESSION: AN OPTIMIZATION ALGORITHM AND ITS STATISTICAL PROPERTIES
• Subset selection for matrices in spectral norm
• Sparse regression using mixed norms
• Subset selection for matrices by volume sampling
• Fitting sparse linear models under the sufficient and necessary condition for model identification

This page was built for publication: A note on sparse least-squares regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446076)