Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of recovering a rank $r$ matrix $X$ in $\mathbb{R}^{d\times d}$ under possibly corrupted linear measurements. The paper studies the non-convex formulation, first considered by [Jianhao Ma, 2021], that uses a overspecified factorization of the unknown matrix and employs an $\ell_1$ minimization. The goal is to recover $X$ by recovering a matrix $F\in \mathbb{R}^{d\times k}$ such that $X = FF^\intercal$, with $k$ possibly bigger than $r$. The authors introduce a Restricted Direction Preserving Property (RDPP), which describes the alignment of the sub-differential of the $\ell_1$ loss function with gradient of the expectation of the loss function. The authors show that RDPP holds for random measurements with certain corruption models and use this to show that the low-rank matrix can be exactly recovered with high probability using a sub-gradient descent method that using diminishing step-size. The result requires number of measurements on the order of $O(dk^3)$, up to log factors and convergence is linear in the case $k = r$. Bulk of the paper rests on the theoretical exposition.  I did not go through the theoretical proofs from the supplementary material in detail, however the proof sketch from the main paper provides sufficient intuition.

main_review: 1. It is not immediately clear, by reading the introduction section, that the corruptions considered in the paper are sparse. In line 32, the authors state "in many cases corruptions $s_i$ are sparse" which falsely implies to the readers that corruptions considered in the paper could be dense and the result presented applies to this general case. Sparsity of corruptions should be made clear before stating the contributions and to motivate the $\ell_1$ formulation presented in the paper.

2. In contribution (exact recovery with rank overspecification) and in abstract, randomness (Gaussian) of the measurement is not stated. This falsely leads the readers to believe that the result applies to general measurements (for example, subsampled Fourier measurements). To my knowledge, the measurements considered in the paper is random. 

3. The measurement matrices considered in the paper are generated from Gaussian Orthogonal Ensemble. How practical is this assumption? This is more restrictive than standard Gaussian measurement. Does a similar recovery result hold of standard Gaussian measurement (with entries i.i.d. $\mathcal{N}(0,1)$?

4. In line 135, it is stated that "generic sensing matrices satisfy RDPP". What are the class of matrices that satisfy RDPP? Can the result be extended to more realistic scenarios where measurements don't follow this property?

5. The subgradient algorithm studied in the paper is initialized using a spectral initialization, which generals involves computing the SVD of a matrix. This problem was reduced to computing eigenvalues/eigenvectors of a matrix because the measurement matrices were symmetric. In Line 60-61, the authors state that their algorithm "does not require SVD" which seems to be not entirely true (at least the initialization requires SVD). This should be made clear.

6. The sample complexity required for successful recovery is on the order of $O(dk^3)$, up to log factors, which is not optimal. This should be discussed in the paper, providing comparison to other related works.

7. There are some words missing or unclear phrasing in Line 63 and Line 147.



limitations_and_societal_impact: Limitations of the paper is discussed in the concluding section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies the problem of recovering a low-rank matrix from grossly corrupted linear measurements. Specifically, the authors analyze an $\ell_1$ empirical risk minimization problem by parameterizing the unknown matrix via the factorization $FF^T$, where the inner dimension of $FF^T$ can be over-specified (i.e., larger than the ground truth rank $r$). The authors show that rigorous recovery guarantees are possible in both the exact specification and over-specified case with a sufficiently small amount of corruption. Subgradient descent with proper initialization and an adaptive step-size can exactly recover the low-rank matrix at a sublinear rate and linear rate in the over-specified and exactly specified case, respectively. To prove this, the authors introduce a regularity condition, called the Restricted Direction Preserving Property (RDPP), and show that satisfaction of this condition is sufficient for subgradient descent to succeed, as this condition essentially states that subgradients behave like their expectations. Experiments show that the proposed algorithm works comparably well to other descent methods with decaying step-size schedules and also that decaying step-sizes could potentially help the Deep Image Prior (DIP) from overfitting to sparse corruptions.
main_review: # Originality

The proposed work provides a new sufficient condition on the measurement matrix and corruption statistics that is a variant of previous work on robust matrix sensing. While the RDPP is similar cosmetically to previous work, the novelty lies in the result that it is shown to be sufficient for local convergence of a subgradient descent algorithm with adaptive step sizes. Moreover, this convergence holds for general rank $r$ ground truth matrices and rank over-specification $k \geqslant r$. 

# Quality
 
- Strengths: - The work is well-written and easy to follow. - The results hold for general rank $r$ and any amount of over-specification $k \geqslant r$. - The proposed algorithm can exactly recover the underlying low-rank matrix in the presence of sparse corruptions, and convergence rates on the algorithm are shown.

- Weaknesses: - The results require spectral initialization, although the initial error bound in the present work is less stringent in previous works. Experimentally, was the spectral initialization scheme necessary for subGD with the proposed step sizes to converge? The case $k = d$ used random initialization with small norm, but the over-specified and exact rank case all used spectral initialization. - The overall sample complexity of the convergence results appears off by a large factor of $k^2$. Could the authors comment on where this bottleneck arises and where the difficulty lies? This may be helpful for the reader to know where potential improvements could be made. It appears this factor is due to the sample complexity required for the RDPP, as it scales like $\delta^{-4}$, and the theory requires $\delta \leqslant 1/\sqrt{k}$.

# Clarity

I found the paper easy to follow, and gained a good amount of intuition from the proof sketches and discussion of results. 

- Typos: pg 1 line 13 “adversary sparse” -> “adversarial sparse”, pg 3 line 112 “facterized” -> “factorized”, pg 3 line 117 “dynamic” -> “dynamics”, pg 5 line 164 is missing a period

Other comments:

- I believe that the proof of Proposition 2.2 is in Appendix C instead of D.
- Eq (2.1) should have $y_i$ instead of $s_i$.
- The results shown for DIP are certainly interesting, but the proposed method wasn’t used in this setting (namely the adaptive step sizes). Thus the sentence on pg 2 line 57-58 may be misleading (instead one could simply note robustness to overfitting for DIP is shown with decaying step sizes). Along these lines, is there an analogous adaptive step-size rule that could be used for denoising with sparse corruptions for the DIP (say, simply taking the median of the measurements)?
- The authors commented on how analyzing other measurement matrices would be an interesting avenue for future work. Along similar lines, could the RDPP (or a variant thereof) potentially have applications to other inverse problems as well?

# Significance

The present work adds an interesting contribution to providing rigorous guarantees for the over-specified matrix sensing setting. This setting is important as, in practice, one would rarely know the exact rank of the ground-truth matrix. 
limitations_and_societal_impact: As the work is theoretical in nature, there are no foreseeable societal impacts. Some limitations on the theory are discussed near the end, and one I would add here is the sub-optimal sample complexity scaling.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the problem of low-rank P.S.D matrix recovery in the presence of outliers. In particular, the paper studies a subgradient method to solve the above problem. The authors firstly define the notion of restricted direction preserving property (and show that this holds for the usual Gaussian measurements) and then propose a different rule for diminishing step size. With these conditions, the paper shows that even in the case of rank-overspecification, the method converges (linearly in certain settings) to the ground truth. The authors also perform some numerical experiments that corroborate the claims. 
main_review: Overall I think this is a fantastic paper with very impressive results. To the best of my knowledge, the results claimed in the paper are very novel in the area, and are a great addition to the literature on low-rank matrix recovery. The problem studied is an important one that has several applications, and a rich literature. I have a few minor comments/questions to the authors that I list below:

- The particular problem is for the low-rank matrix recovery problem, if one were interested in low-rank matrix completion, can the authors comment something about the RDPP for say random bernoulli/uniform random sampling sort of matrices? 

- The wording of the two settings on $s_i$'s (Def.  Model1, 2) is a bit confusing and can be improved to highlight the differences better 

- In Def 2.1, if $\psi(X)$ is just a scalar, why use a function notation at all? 

- There are some discrepancies in $D(X)$ and $\mathcal{D}(X)$ throughout the paper.

- Are the entries in Table 2 based on a Monte-Carlo averaging? Also table 2 seems to contradict the results of [13] which claim (in an order notation at least) that Gaussians satisfy sign-RIP? I believe including a few settings where sign-RIP holds would improve the exposition of the paper. 

- I also think that given the close connection with sign-RIP a more detailed discussion (the paragraph following Table 2) regarding these properties is warranted. 

- In the expectation discussion below (3.2), what is the expectation taken over? because there are potentially several sources of randomness. 

- this is just a question out of curiosity: so since there is some implicit regularization that is happening, would the authors be able to comment on how the stable rank of $F_t F_t^\top$ evolves over iterations? 

limitations_and_societal_impact: Please see above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of recovering a positive semi-definite matrix from a set of corrupted measurements, under the setup that the rank of the target matrix is unknown. Based on some Gaussian assumptions on the sensing matrices and the corruption model, the authors prove that the nonconvex program (1.2) equipped with a subgradient algorithm can achieve exact recovery. The key to accomplish the proof is a new regularity condition called Restricted Direction Preserving Property (RDPP).
main_review: 1. Recently, tremendous attention has been attracted by the theoretical side of non-convex optimization based robust low-rank matrix recovery. Though I don't understand why that happens, this submission truly makes some progress in the direction: they resolve the issues raised by over-specified rank on the target matrix.   

2. The paper is well-written. In fact, this paper is an improved version of another submission entitled "Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery", with the same problem space and similar techniques. For the Sign-RIP paper, I have concerns about the rationality of its claims and justifications. The statements and claims in this submission are adequate, thereby I vote for acceptance.

3. The importance of low-rank matrix recovery could be made more convincing. Besides the well-known applications such as image analysis, I have seen some recent papers that apply recovery methodology to the filed of time series forecasting, e.g., "Recovery of Future Data via Convolution Nuclear Norm Minimization", "Time Series Forecasting via Learning Convolutionally Low-Rank Models".
limitations_and_societal_impact: The assumption on the sensing matries is very restrictive, and the authors have adequately addressed this in Section 5.
review_title: null

Meta-review: There is a consensus among the reviewers that this paper presents significant results of interest to the conference. 
Decision: Accept (Poster)