Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work combines stable Principal Component Pursuit and Square Root Lasso and proposes Square Root Principal Component Pursuit for low-rank + sparse recovery problem. Compared to stable PCP, Square Root PCP has the advantage that the choice of the regularization parameter is noise-independent, so it is easier to be deployed in applications where the noise level is unknown. Theoretical analysis and experiments confirm the effectiveness of the proposed method.
main_review: Overall, this is a well written paper. It contains theoretical analysis that with a single, universal choice of the regularization parameter, the low-rank matrix and the sparse matrix can be stably recovered. ADMM is applied to solve Square Root PCP with details such as initializations and stopping criteria. This paper also contains experiments in different settings and they confirm the effectiveness of the proposed method.

I am also satisfied with the improvements made for this resubmission. I have only one comment:

There are some existing works using ADMM to solve Square Root Lasso and it is worth citing them in this paper:
- The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in R by Xingguo Li et al.
- Square-Root lasso with nonconvex regularization: An ADMM approach by Xinyue Shen et al.
limitations_and_societal_impact: I don't see the limitations in this paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper describes a square-root principal component pursuit for low rank matrix recovery, which is a modification of the original PCP approach in which the original squared Frobenius norm term is replaced with a non-squared term. The paper shows that this change allows one to set the weights of the regularizer in a manner independent of the noise level.
main_review: The notation (L,S) should be defined explicitly - is it a concatenation? It appears inside a Frobenius norm in line 169.

In Lemma 2.3, it is not clear what T, U and V are. Perhaps one should write L0 instead of UV*?

In Algorithm 1, although the proximal operators for ell1 and nuclear norm are well know, it is less clear what the proximal operator for the (non squared) Frobenius norm is. Is it a scaling of the matrix by its Frobenius norm? Adding detail on these would be welcome.

It would be good to discuss why the results in Figure 1(c) show no improvement for root PCP. It would also be good to have numerical comparisons with PCP with real data, perhaps in the supplemental material.
limitations_and_societal_impact: The paper states the noise regimes in which other algorithms exhibit better noise tolerance than the proposed approach; nonetheless, those must be aware of the noise level. Application-dependent social impacts are discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Low-rank matrix recovery in the presence of sparse corruptions and random noise, under incoherence assumptions on the low-rank and on the sparse components, have been considered. Following an existing line of work, a tuning-free optimization programs has been proposed for demixing and denoising. The analysis, utilizing existing techniques, establishes a bound on the reconstruction error. The bound has been observed to be loose by a dimension-dependent factor (according to the experiments and compared to other estimators for this problem). The estimator is a convex optimization problem which authors solve via ADMM.  Numerical experiments support the usefulness of the proposed approach in a set of synthetic and real data scenarios. 
main_review: I believe the work is original (of course, building upon a now well-known idea as in square-root lasso). The manuscript is clear and details have been provided. However, considering existing works on this approach, of design and analysis for a tuning-free regularized estimator, I think further examination is required to establish this proposal as a useful method in practice. 

line 59: I am not sure if the use of 'separable' (which I assume points to the splitting in ADMM) is appropriate. 

The bullet point starting on line 165 seem to be referring to the proof of Theorem 1.1, but is rather technical and vague without further details. A rephrasing of this item could be helpful. 

Proof of Lemma 2.2 in the Appendix has a few broken references. 

Appendix, the equations after (A.3), the third inequality: 
1) bounding r seems to require \nu\geq 1 
2) it seems that 1/520 should be 1/(520 \sqrt{n_1 n_2}), but the fourth inequality is correct. 
I am not sure if I understand why A.5 holds. Otherwise, the rest of the proof goes through. 

line 245: could you please elaborate on how the plot has been interpreted as O(\sigma)? 
Moreover, the plots suggest a concave trend (authors concluded a linear trend; lines 246, 276). Any insights would be appreciated. 

The visual inspections in sections 4.3 and 4.4 are difficult; Figures 3 and 4. Alternative presentation of the intended results and conclusions could be helpful. 

It might be helpful to discuss the 'limitations' incurred by the homogeneity of the objective function (discussed on lines 106-112); for example in tuning or solving the optimization problem, etc. 

Do the authors have any intuition on the dimension-dependent factor in their bound? (lines 132-133, 159)

limitations_and_societal_impact: The proposal is a natural continuation on the idea behind the square root lasso and a few other tuning-free estimators. While such continuation of the underlying idea is undoubtedly valuable, I think a thorough examination of other aspects (beyond the design and the analysis of the estimator; e.g., tuning, computation, runtime, etc) could add further unique value. I believe the authors have already covered a number of interesting aspects (a bound, an algorithm, and the numerical experiments: varying mu, comparing the solutions themselves, etc). However, some further aspects could enhance the paper. Here are a few suggestions:
- comparing the actual running time of 1) the other two formulations including their hyperparameter tuning 2) with the current proposal considering the quality of solutions (in an appropriae metric) and the possible need for tuning \mu (to improve the quality of the solution); considering the comparable performance reported in Figure 1 in the Appendix, etc. It would be helpful to see such comparison in various data regimes. 
- further discussions on the dimension-dependent factor. 
- experiments with different noise distributions (which affects the range for \sigma), closer to the distributions in real data (vision or others). 



======================== Update

I have read the other reviews as well as the responses. I would like to thank the authors for their clear explanations. I think the proposed additions are satisfactory; except for the explanations in regards to:

1) the sub-optimality of the bound, where I would like to (not necessarily as part of this review process) see further intuitions and arguments beyond the mechanics of the current proof. 

2) the presented experiments. I apologize as I can see that my original comment (the first bullet point in the above) is not very clear. What I meant was to suggest examining a possible scenario in which sqrt-PCP becomes overall computationally-expensive due to a requirement for tuning mu (motivation: sqrt-PCP has an additional non-smoothness compared to PCP, and, ADMM is a choice which requires examination). Let me elaborate: 

It would be helpful if the authors could use a clear metric(s) for the the quality of the solutions (at the moment, in the Appendix, there are errors reported in Tables 1,2, and there are figures that are not easy to compare quantitatively) and then report wall-clock times for all three algorithms to achieve pre-specified levels of accuracy according to said metric (at the moment, the numbers in Tables 1,2, while comparable between the corresponding cells in the two tables, seem rather arbitrary). Note that in the second step, the desired accuracy determines the length of search for an appropriate mu. Tuning mu, if needed, would increase the wall-clock time for sqrt-PCP, and allows for understanding the limitations of the tuning-free estimator and the solver (e.g., in high-accuracy scenarios). Note that in this experimental setup, tuning for mu is not a choice but is rather dictated by the noise and the desired accuracy level. Finally, considering various data regimes allows for examining the above question when starting the search with the data-agnostic choice of mu=sqrt(n_2/2). 

I would like to emphasize that this suggestion is only to 'stress' the system in order to understand its limitations, and I would understand if the authors believe this is outside the scope of this work. However, I believe such examination is important in supporting the tuning-free claim for the proposal (in conjunction with the theoretical bounds). It would be nice to hear the authors' thoughts and whether I am missing a technical aspect in making this suggestion.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Motivated from square-root Lasso, this paper propose a new tuning-free convex program, called SR-PCP, to solve low-rank matrix recovery problem from observations corrupted by sparse outliers and dense noise.
main_review: Strengths:
1. This paper proposes a new program which has appealing tuning-free property, and also provide theoretical guarantees as well as an ADMM algorithm to solve it. The theory is solid, and the paper is clearly written.
1. SR-PCP improves the prior work [8] in the sense that one does not need to tune the regularization parameter, which either requires to estimate the noise level (which might be difficult) or using cross-validation (which lacks theoretical guarantee). Although the idea is not new (which originates from square-root lasso [11]), but it is still meaningful to introduce this idea to the field of low-rank matrix recovery.
2. The authors proved stability bounds SR-PCP which scales with the noise level. This stability bound guarantees exact recovery when there is no noise, even in the presence of outliers.

Weakness:
The main weakness of this paper, as the authors mentioned in Section 1.3, is that their estimation error bound is sub-optimal by a dimension-dependent factor. I think it would be better if the authors can provide more explanation on why this sub-optimality occurs compared to prior works, and if it is possible to generlize the proof of this paper to achieve the optimal rates.
limitations_and_societal_impact: This is a theoretical work, and I think there is no potential societal impact.
review_title: null

Meta-review: The paper studies the low-rank matrix recovery problem from observations corrupted by noise and sparse outliers. It proposes a framework called square root principal component pursuit, which is a combination of stable principal component pursuit and square root Lasso. The proposed technique has the advantage that the choice of the regularization parameter is noise-independent, so it is easier to be deployed in applications where the noise level is unknown. The main concern is about the estimation error bound obtained in the paper which is sub-optimal by a dimension-dependent factor. More explanation on why this sub-optimality occurs compared to prior works should be provided. 
Decision: Accept (Poster)