Column subset selection via sparse approximation of SVD (Q764372)

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\).