CS: A Single-letter Characterization of Optimal Noisy Compressed Sensing, Low-rank Matrix Completion, Uniqueness of Low-Rank Matrix Completion

Today, we have a potentially far reaching article and two other papers on matrix completion. Enjoy!

Dongning Guo, Dror Baron, and Shlomo Shamai, introduce us to A Single-letter Characterization of Optimal Noisy Compressed Sensing. The abstract reads:

Compressed sensing deals with the reconstruction of a high-dimensional signal from far fewer linear measurements, where the signal is known to admit a sparse representation in a certain linear space. The asymptotic scaling of the number of measurements needed for reconstruction as the dimension of the signal increases has been studied extensively. This work takes a fundamental perspective on the problem of inferring about individual elements of the sparse signal given the measurements, where the dimensions of the system become increasingly large. Using the replica method, the outcome of inferring about any fixed collection of signal elements is shown to be asymptotically decoupled, i.e., those elements become independent conditioned on the measurements. Furthermore, the problem of inferring about each signal element admits a single-letter characterization in the sense that the posterior distribution of the element, which is a sufficient statistic, becomes asymptotically identical to the posterior of inferring about the same element in scalar Gaussian noise. The result leads to simple characterization of all other elemental metrics of the compressed sensing problem, such as the mean squared error and the error probability for reconstructing the support set of the sparse signal. Finally, the single-letter characterization is rigorously justified in the special case of sparse measurement matrices where belief propagation becomes asymptotically optimal.

Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison by Raghunandan Keshavan, Andrea Montanari and Sewoong Oh. The abstract reads: 

We consider a problem of significant practical importance, namely, the reconstruction of a low-rank data matrix from a small subset of its entries. This problem appears in many areas such as collaborative filtering, computer vision and wireless sensor networks. In this paper, we focus on the matrix completion problem in the case when the observed samples are corrupted by noise. We compare the performance of three state-of-the-art matrix completion algorithms (OptSpace, ADMiRA and FPCA) on a single simulation platform and present numerical results. We show that in practice these efficient algorithms can be used to reconstruct real data matrices, as well as randomly generated matrices, accurately.

The software is here while the slides of the presentation are here.

Finally, we have: Uniqueness of Low-Rank Matrix Completion by Rigidity by Amit Singer and Mihai Cucuringu. The abstract reads:

The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision and control. Most recent work had been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic point of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to efficient randomized algorithms for testing necessary and sufficient conditions for local completion and for testing sufficient conditions for global completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix.

Credit: NASA, This image was taken with the LCROSS visible light context camera Aug. 17, 2009, from a distance of approximately 323,296 miles (520,294 km) from the Earth and 547,335 miles (880,850 km) from the moon. In this view, the Earth and moon are separated by approximately 4.8 degrees. The red/blue speckled pixels within the VIS camera are caused by cosmic ray radiation in space, and are not stars. The Centaur part of LCROSS will be smashing the moon in full force on October 9th, 3 days from now. It's going to be a nice show at 5:30 Central time.