CS: A Matrix Completion Entry

After Friday's entry on the subject, here some more matrix completion cods and papers:Yi Ma just sent me the following:

You may want to check out our new website dedicated for low-rank matrix recovery and completion at:

http://perception.csl.illinois.edu/matrix-rank/home.html

Matrix recovery (also known as robust PCA) is arguably a more difficult problem that matrix completion and it reveals some nice tradeoff between rank and sparsity. On the website we gather all up to date work on theory, algorithms, and applications (soon). We also provide the code for the fastest algorithms know todate for both matrix recovery and completion.

I note that they list the other matrix completion approaches here.

and then we have: A Simpler Approach to Matrix Completion by Benjamin Recht. The abstract reads:

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

and Compressed Quantum Process Tomography by Alireza Shabani, R. L. Kosut, Herschel Rabitz. The abstract reads:

The characterization of a decoherence process is among the central challenges in quantum physics. A major difficulty with current quantum process tomography methods is the enormous number of experiments needed to accomplish a tomography task. Here we present a highly efficient method for tomography of a quantum process that has a small number of significant elements. Our method is based on the compressed sensing techniques being used in information theory. In this new method, for a system with Hilbert space dimension n and a process matrix of dimension n^2 x n^2 with sparsity s, the required number of experimental configurations is O(s log n^4). This heralds a logarithmic advantage in contrast to other methods of quantum process tomography. More specifically, for q-qubits with n=2^q, the scaling of resources is O(sq) linear in the product of sparsity and number of qubits.