Recovering Low-Rank Matrices From Few Coefficients In Any Basis

Recovering Low-Rank Matrices From Few Coefficients In Any Basis

17 Sep 2010 | David Gross
This paper presents novel techniques for analyzing the problem of low-rank matrix recovery. The methods are simpler and more general than previous approaches. It is shown that an unknown n×n matrix of rank r can be efficiently reconstructed from only O(nrν ln²n) randomly sampled expansion coefficients with respect to any given matrix basis. The parameter ν quantifies the "degree of incoherence" between the unknown matrix and the basis. The result covers the special case of matrix completion, where a low-rank matrix is recovered from randomly selected matrix elements. The proof consists of elementary steps, contrasting with previous complex methods. The bounds are slightly tighter than known results. The paper discusses operator bases that are incoherent to all low-rank matrices, showing that O(nrν ln n) coefficients suffice to recover any low-rank matrix with high probability. The result is tight up to multiplicative constants. The paper introduces a new approach to low-rank matrix recovery, focusing on the problem of recovering a low-rank matrix from a small number of expansion coefficients with respect to some basis. The key idea is to use a convex optimization algorithm to reconstruct the matrix from the coefficients. The paper defines the concept of coherence, which measures the incoherence between the unknown matrix and the basis. The main result shows that a low-rank matrix can be uniquely recovered from a certain number of coefficients, provided the basis is incoherent with the matrix. The paper also discusses the implications of the results for quantum-state tomography and provides a detailed proof of the main result. The paper concludes with a discussion of the implications of the results for the broader field of matrix recovery and compressed sensing.This paper presents novel techniques for analyzing the problem of low-rank matrix recovery. The methods are simpler and more general than previous approaches. It is shown that an unknown n×n matrix of rank r can be efficiently reconstructed from only O(nrν ln²n) randomly sampled expansion coefficients with respect to any given matrix basis. The parameter ν quantifies the "degree of incoherence" between the unknown matrix and the basis. The result covers the special case of matrix completion, where a low-rank matrix is recovered from randomly selected matrix elements. The proof consists of elementary steps, contrasting with previous complex methods. The bounds are slightly tighter than known results. The paper discusses operator bases that are incoherent to all low-rank matrices, showing that O(nrν ln n) coefficients suffice to recover any low-rank matrix with high probability. The result is tight up to multiplicative constants. The paper introduces a new approach to low-rank matrix recovery, focusing on the problem of recovering a low-rank matrix from a small number of expansion coefficients with respect to some basis. The key idea is to use a convex optimization algorithm to reconstruct the matrix from the coefficients. The paper defines the concept of coherence, which measures the incoherence between the unknown matrix and the basis. The main result shows that a low-rank matrix can be uniquely recovered from a certain number of coefficients, provided the basis is incoherent with the matrix. The paper also discusses the implications of the results for quantum-state tomography and provides a detailed proof of the main result. The paper concludes with a discussion of the implications of the results for the broader field of matrix recovery and compressed sensing.
Reach us at info@study.space