CS: A singular thresholding algorithm for matrix completion, Bayesian Compressive Sensing update, Compressive Sensing Hardware

This is a first for me, the three authors of a preprint have updated their own webpage the same day of the preprint's release. Jainfeng Cai, Emmanuel Candès and Zuowei Shen just made available A singular thresholding algorithm for matrix completion. (One can also find it also here, here, or here on ArXiv). The abstract reads:

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem, and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative and produces a sequence of matrices {X_k;Y_k} and at each step, mainly performs a soft-thresholding operation on the singular values of the matrix Y_k. There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates {X_k} is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which 1,000 x1,000 matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are connected with the recent literature on linearized Bregman iterations for l_1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.

It is not strictly related to compressive sensing but improves on a previous paper and on another concept that sought to make the parallel between rank minimization and nuclear norm minimization using random linear combination of the unknown matrix (a la CS). In a similar vein, Thong Do, Yi Chen, Nam Nguyen, Lu Gan and Trac Tran recently presented a way to do this with Struturally Random Matrices. The main difference between these two latter approaches and that taken by the present paper is that in this paper by Jainfeng Cai, Emmanuel Candès and Zuowei Shen, one has a direct access to specific elements of the matrix. In the latter approaches, using either gaussian or SRM matrices, one has access to only a linear combination of the unknown elements of the matrix. In generic cases of interest, one has generally access to single elements of the otherwise unknown matrix, which makes this paper very interesting. I for one keep wondering in the back of my mind how the gaussian or SRM linear mapping could have an equivalent in the physical world.


My webcrawler noticed that in the Bayesian Compressive Sensing website. There is a mention of the fact that the BCS code was updated on Aug. 03, 2008 as a bug was fixed in MT_CS.m for the cases where signals were dramatic undersampled.

Finally, I have tried my best to make a compilation of most of the hardware implementation developed with compressive sensing in mind. It is here:

http://igorcarron.googlepages.com/compressedsensinghardware

Sometimes, off-the shelf hardware can be used to do compressed sensing with no hardware change but with a different mode of operation (case of the Herschel observatory or the Chinese Chang'e probe), otherwise there is hardware developed to perform sampling in a different kind of way but is not specifically using compressed sensing ( like the hardware developed in computational photography or the coded aperture work) but should !. For the time being, I am not adding the latter equipment but soon will and I don't know how to address the former. I am also trying to categorize each of these technologies with regards to their respective Technology Readiness Level (also mentioned here in a french entry). Some way to do is by using the Excel spreadsheet of the latest TRL Calculator.