Column subset selection via sparse approximation of SVD
type: Item
instance of: scholarly article
title: Column subset selection via sparse approximation of SVD
zbMATH Open document ID: 1238.65030
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
review text: The authors attempt to solve a simultaneous sparse approximation problem where there are \(k\) signals to be approximated simultaneously from the dictionary spanned by a matrix \(A\). When the columns of \(A\) have specific meaning, it might be desirable to find good approximations to \(A_k\) which use a small number of columns of \(A\). The following theorem provides a greedy algorithm in the Frobenius norm. Given a matrix \(A\in{\mathbb R}^{m\times n}\), an integer \(k<r=\text{rank}(A)\) and \(\epsilon<\|A_k\|_F/\|A-A_k\|_F\), there exists a polynomial-time algorithm which selects a column sub-matrix \(C\in{\mathbb R}^{m\times c}\) of \(A\) with \(c=O((k\log k/\epsilon^2)\eta^2(A)\ln(\|A_k|_F/\epsilon\|A-A_k\|_F))\) columns such that \(\|A-\Pi_C A\|_F\leq (1+\epsilon)\|A-A_k\|_F\) where \(C\) is the matrix composed of the \(c\) columns, \(\Pi_C\) is the matrix projecting the columns of \(A\) onto the space spanned by \(C\) and \(\eta(A)\) is a measure related to the coherence in the normalized columns of \(A\).
reviewed by: Rémi Vaillancourt
Mathematics Subject Classification ID: 65F20
zbMATH DE Number: 6014342
zbMATH Keywords: subset selection
zbMATH Keywords: sparse approximation
zbMATH Keywords: singular value decomposition (SVD)
zbMATH Keywords: greedy algorithm
zbMATH Keywords: polynomial-time algorithm
author: Ali Çivril
author: Malik Magdon-Ismail
describes a project that uses: svdpack
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.11.019
OpenAlex ID: W2062570725
cites work: Fast computation of low rank matrix approximations
cites work: Q4633910
cites work: From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
cites work: Handbook series linear algebra. Linear least squares solutions by Householder transformations
cites work: Rang revealing QR factorizations
cites work: Low‐rank revealing QR factorizations
cites work: On Rank-Revealing Factorisations
cites work: Theoretical Results on Sparse Representations of Multiple-Measurement Vectors
cites work: Adaptive greedy approximations
cites work: Subset selection for matrices
cites work: Sampling-based dimension reduction for subspace approximation
cites work: Adaptive Sampling and Fast Low-Rank Matrix Approximation
cites work: Q4252300
cites work: Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
cites work: Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
cites work: Relative-Error $CUR$ Matrix Decompositions
cites work: Fast monte-carlo algorithms for finding low-rank approximations
cites work: Q5689624
cites work: Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
cites work: Q5365143
cites work: Rank-Revealing QR Factorizations and the Singular Value Decomposition
cites work: Numerical Linear Algebra
cites work: Vector greedy algorithms
cites work: Sparse Approximate Solutions to Linear Systems
cites work: Bounds on singular values revealed by QR factorizations
cites work: Random vectors in the isotropic position
cites work: Sampling from large matrices
cites work: Q2934635
cites work: Smoothed analysis of algorithms
cites work: Greed is Good: Algorithmic Results for Sparse Approximation
cites work: Algorithms for simultaneous sparse approximation. I: Greedy pursuit
DOI: 10.1016/J.TCS.2011.11.019
description: scientific article; zbMATH DE number 6014342