CS: On Low Rank Matrix Approximations with Applications to Synthesis Problem in CS, Learning Sparse Systems, ADM for NMF, Proximal Splitting Methods,

To finish this week, here are several papers directly or not so directly related to compressive sensing. Enjoy!

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing by Anatoli Juditsky, Fatma Kilinc Karzan, Arkadii S. Nemirovski. The abstract reads:

We consider the synthesis problem}of Compressed Sensing - given s and an MXn matrix A, extract from it an mXn submatrix A', certified to be s-good, with m as small as possible. Starting from the verifiable sufficient conditions of s-goodness, we express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm. We propose randomized algorithms for efficient construction of rank k approximation of matrices of size mXn achieving accuracy bounds O(1)sqrt({ln(mn)/k) which hold in expectation or with high probability. We also supply derandomized versions of the approximation algorithms which does not require random sampling of matrices and attains the same accuracy bounds. We further demonstrate that our algorithms are optimal up to the logarithmic in m and n factor. We provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

Learning Sparse Systems at Sub-Nyquist Rates: A frequency-Domain Approach by Martin McCormick, Yue M. Lu and Martin Vetterli. The abstract reads:

We propose a novel algorithm for sparse system identification in the frequency domain. Key to our result is the observation that the Fourier transform of the sparse impulse response is a simple sum of complex exponentials, whose parameters can be efficiently determined fromonly a narrowfrequency band. From this perspective, we present a sub-Nyquist sampling scheme, and show that the original continuous-time system can be learned by considering an equivalent low-rate discrete system. The impulse response of that discrete system can then be adaptively obtained by a novel frequency-domain LMS filter, which exploits the parametric structure of the model. Numerical experiments confirm the effectiveness of the proposed scheme for sparse system identification tasks.

An Alternating Direction Algorithm for Nonnegative Matrix Factorization by Yin Zhang, The abstract reads:

We extend the classic alternating direction method for convex optimization to solving the non-convex, nonnegative matrix factorization problem and conduct several carefully designed numerical experiments to compare the proposed algorithms with the most widely used two algorithms for solving this problem. In addition, the proposed algorithm is also briefly compared with two other more recent algorithms. Numerical evidence shows that the alternating direction algorithm tends to deliver higher-quality solutions with faster computing times on the tested problems. A convergence result is given showing that the algorithm converges to a Karush-Kuhn-Tucker point whenever it converges.

Proximal Splitting Methods in Signal Processing by Patrick L. Combettes, and Jean-Christophe Pesquet. The abstract reads:

The proximity operator of a convex function is a natural extension of the notion of a projection operator onto a convex set. This tool, which plays a central role in the analysis and the numerical solution of convex optimization problems, has recently been introduced in the arena of signal processing, where it has become increasingly important. In this paper, we review the basic properties of proximity operators which are relevant to signal processing and present optimization methods based on these operators. These proximal splitting methods are shown to capture and extend several well-known algorithms in a unifying framework. Applications of proximal methods in signal recovery and synthesis are discussed.

Piotr Indyk has a talk on Sparse Recovery Using Sparse Matrices, given in various forms in various places.

Holger Rauhut has some lecture notes entitled Compressive sensing and structured random matrices. These lecture Notes are still under construction. If you have comments of any sort, he would be happy to receive them.