Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity

Overview

• This paper explores two classes of algorithms for reconstructing a low-rank matrix from a few linear measurements.
• Convex approaches based on nuclear norm minimization are known to recover the ground truth when the number of samples scales linearly with the degrees of freedom.
• Non-convex approaches using factorized gradient descent are computationally less expensive but require the number of samples to scale quadratically with the rank.
• The paper aims to close this gap by showing that non-convex approaches can be as efficient as nuclear norm minimization in terms of sample complexity.

Plain English Explanation

The researchers are studying how to reconstruct a low-rank matrix (a matrix that can be well-approximated by a matrix of lower rank) from a small number of measurements. There are two main approaches to this problem:

1. Convex Optimization: These methods try to find the matrix with the smallest "nuclear norm" (a measure of the matrix's complexity) that is consistent with the observed measurements. This approach is known to work well when the number of measurements scales linearly with the "degrees of freedom" of the true matrix.

2. Non-convex Optimization: These methods use an iterative, gradient-based approach to directly optimize a non-convex objective function. While computationally cheaper, existing guarantees for these methods require the number of measurements to scale quadratically with the rank of the true matrix.

In this paper, the researchers show that non-convex methods can actually be as efficient as convex methods in terms of the required number of measurements. They consider the specific case of reconstructing a positive semi-definite matrix from Gaussian measurements, and demonstrate that a factorized gradient descent approach with spectral initialization can recover the true matrix with a linear convergence rate, as long as the number of measurements scales linearly with the rank, the dimension, and the condition number of the true matrix.

The key insight in their proof is a "probabilistic decoupling" argument, which shows that the iterates of the gradient descent algorithm are only weakly dependent on the individual entries of the measurement matrices. This technical result may be useful for analyzing other non-convex optimization problems.

Technical Explanation

The researchers consider the problem of reconstructing a low-rank positive semi-definite matrix $X \in \mathbb{R}^{d \times d}$ from a small number of linear measurements $y = \mathcal{A}(X)$, where $\mathcal{A}: \mathbb{R}^{d \times d} \to \mathbb{R}^{m}$ is a linear measurement operator.

Two main classes of algorithms have been studied for this problem:

1. Convex Approaches: These methods solve a nuclear norm minimization problem of the form $\min_Z |\mathcal{A}(Z) - y|

   $ denotes the nuclear norm. Under certain statistical assumptions, it is known that this approach recovers the ground truth as soon as the number of samples $m$ scales linearly with the degrees of freedom of $X$, i.e., $m \gtrsim rd$, where $r$ is the rank of $X$.

2. Non-convex Approaches: These methods use a factorized representation $X = UU^\top$, where $U \in \mathbb{R}^{d \times r}$, and perform gradient descent on the factors $U$. While computationally more efficient, existing guarantees for these methods require $m \gtrsim r^2 d$, i.e., the number of samples scales quadratically with the rank.

In this paper, the researchers show that non-convex approaches can be as efficient as convex approaches in terms of sample complexity. Specifically, they consider the case where $X$ is positive semi-definite, and the measurement operator $\mathcal{A}$ applies Gaussian random projections. They show that factorized gradient descent with spectral initialization converges to the ground truth with a linear rate as soon as $m \gtrsim rd \kappa^2$, where $\kappa$ is the condition number of $X$.

The key technical contribution is a "probabilistic decoupling" argument, which shows that the gradient descent iterates are only weakly dependent on the individual entries of the measurement matrices. This allows the researchers to obtain tighter bounds on the sample complexity compared to previous analyses of non-convex methods.

Critical Analysis

The paper presents an important result that narrows the gap between the sample complexity of convex and non-convex approaches for low-rank matrix reconstruction. By showing that non-convex methods can be as efficient as convex methods under certain conditions, the researchers have expanded the toolbox available for solving these types of problems.

However, it's worth noting that the analysis is specific to the case of positive semi-definite matrices and Gaussian measurements. It's unclear whether the "probabilistic decoupling" argument would extend to more general measurement operators or matrix structures. Additionally, the dependence on the condition number $\kappa$ of the ground truth matrix may be a limiting factor in practical applications, where the condition number may be large.

Further research could explore whether similar efficiency improvements can be achieved for non-convex methods in other matrix reconstruction problems, such as those involving non-negative or sparse matrices. Additionally, investigating the robustness of these non-convex approaches to model misspecification or adversarial attacks could be an interesting direction for future work.

Overall, this paper represents an important step forward in our understanding of the relative strengths and limitations of convex and non-convex methods for low-rank matrix reconstruction problems.

Conclusion

This paper bridges the gap between convex and non-convex approaches for reconstructing a low-rank positive semi-definite matrix from a small number of linear measurements. The researchers show that a non-convex, factorized gradient descent method with spectral initialization can be as efficient as nuclear norm minimization in terms of sample complexity, as long as the number of measurements scales linearly with the rank, dimension, and condition number of the ground truth matrix.

This result expands the toolbox available for solving low-rank matrix reconstruction problems, which arise in a variety of applications, such as system identification, image processing, and machine learning. The key technical insight of "probabilistic decoupling" may also prove useful for analyzing other non-convex optimization problems. While the analysis is limited to positive semi-definite matrices and Gaussian measurements, this work represents an important step towards bridging the gap between convex and non-convex approaches in matrix reconstruction.