Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares

Summary

This paper proposes an IRLS method for recovering data with multiple, heterogeneous low-dimensional structures from linear observations. It combines non-convex surrogates for row-sparsity and rank, to identify simultaneously row-sparse and low-rank matrices from limited measurements. Theoretical results are provided that show locally quadratic convergence. The experiments demonstrate favorable empirical convergence and prove its efficacy in handling challenging data recovery scenarios.

Strengths

The paper is well-written overall and the contributions are clear. The challenge of the combination of structures is made apparent. The related work discussion is thorough. The IRLS is a popular approach and is practical even for large-scale systems. Experiments suggest the method is also robust to the choice of parameters r and s.

Weaknesses

Although it is also true of other results in this area, only local convergence is guaranteed and practically it may be challenging to guarantee an initialization within the required radius. The results would be strengthened if other matrices besides Gaussian were shown to satisfy this RIP, and if others were even just used empirically and shown to still offer convergence.

Questions

It would be good to remind the reader what \cal{F}_ functions are in (13). Are there other matrices besides Gaussian that are known to satisfy the RIP given in Definition 2.3?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors discuss the non-optimality of the bounds in Theorem 2.4, arguing that experimentally the convergence radius appears to be much larger. The authors also discuss future work about generalizing to other combined structures, which the reviewer agrees is interesting future work but certainly not a limitation to the results in this paper.

Summary

This article introduces an algorithm for recovering jointly row-sparse and low-rank matrices from (underdetermined) linear measurements. The algorithm is based on iteratively reweighted least squares for a non-convex objective. The method is theoretically analysed, establishing local quadratic convergence rates under the restricted isometry property. The second theoretical result relates the algorithm more directly to IRLS to show that the objective is non-increasing and proves convergence to a stationary point.

Strengths

I found the paper well-written, the problem of simultaneously recovering sparse and low rank matrices is challenging one cannot simply rely on standard convex regularisation. This work provides a nice solution to this problem via IRLS and the theoretical results are interesting: the authors establish both 'compressed sensing' type results that guarantee recovery under near optimal sampling complexity, as well as results that provide an understanding of the optimisation properties of the algorithm.

Weaknesses

- The numerical results are somewhat limited, it would have been nice to have a discussion on the applications of the proposed method and more realistic numerical examples. - the result of Theorem 2.4 is restricted to the setting of exact measurements and does not cover robustness results, i.e. what if y has been corrupted with noise? Also, what if $X_*$ is only approximately sparse and low rank? Both of these are the more realistic settings, so it would have been nice to see a more complete result. Also, theory aside, equation (1) mentions additive noise, but it is not clear from the algorithm and results that the proposed method can handle additive noise. - Given that the title mentions "simultaneously structured data", I was expecting more than just low rank + sparse. It would be interesting to see the method extended to other kind of structures such as sparsity with respect to some dictionary.

Questions

- can you mention the per-iteration complexity of your method and contrast it with existing methods? - the introduction mentions simultaneously low rank and both column and row sparse. Can your results be extended to this setting?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

Paper proposes to solve inverse problems on matrices subject to multiple types of sparsity (e.g. low-rank and element-wise sparsity) using an algorithm designed for the non-convex objective functions involved. The algorithm is a re-weighted least squares, which despite not solving a convex problem, authors prove a local convergence and a global consistency theorem for. They illustrate the performance of their algorithm on synthetic data.

Strengths

The algorithm proposed solves a difficult non-convex problem, and the theoretical results by authors are original and interesting.

Weaknesses

1. The paper contains statistical results of the type "if at least m measurements are available then the algorithm achieves good performance", but is missing a more thorough discussion on algorithmic complexity. In particular, I would be curious to know if the truncated SVD in the Update Smoothing step is the heaviest computational piece of the algorithm or if the computational bottleneck is somewhere else. 2. Numerical experiments are run on very small data. To really show the benefit of two sparsity types I would believe that bigger values of n1 n2 result in more convincing evidence that there is benefit in mixing the two prior knowledges

Questions

1. what is the sensitivity of the algorithm to performing approximate SVDs 2. Figure 3: fewer iterates are needed, OK, but what's the FLOP in each iterate? what's the overall computational cost of achieving epsilon close results as compared to others? is anything parallelizable? 3. A related stream of research (see Tight Convex Relaxations for Sparse Matrix Factorization, NIPS 2014) characterizes the atoms that form the basis in which a doubly sparse matrix is sparse. How does this work, especially the lower bound Omega(r(s1+s2)), compare to those methods which directly minimize for the desired structure to recover?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

because the computational complexity is not deeply discussed, it's hard to know how applicable the methods are to larger data

Summary

This work studies the problem of recovering a low-rank and row-sparse matrix from its compressed linear observations. A method based on iteratively re-weighted least squares is proposed, in which the sparsity inducing function is a non-convex log function. For theoretical contributions, this work provides a local quadratic convergence analysis of the iterates of the proposed algorithm under a restricted isometry property assumption, and it also studies the convergence of function value for any linear measurement operator using a Majorize-Minimize algorithm framework. Numerical experiments on synthetic datasets show that the proposed method can recover the ground truth with fewer measurements than some state-of-the-art methods.

Strengths

1. This work provides convergence analyses not only for linear operators satisfying restricted isometry property but also for more general linear operators. Furthermore, it mentions when the restricted isometry property can be satisfied, and it also discusses the radius of the neighborhood in the local quadratic convergence. 2. The proposed algorithm is well explained by identifying that the underlying family of objectives that are minimized during the iterations is (2). 3. There are experiments for cases where the rank and sparsity are not accurately known as a prior, and thus the sensitivity to hyper-parameter choice is discussed, and also it provides a better simulation of potential real-world scenarios.

Weaknesses

(1) The algorithm requires estimates of the rank and row sparsity, and the theoretical conclusions require that these estimates are accurate, i.e., $\tilde r = r$ and $\tilde s = s$. These priors and assumptions can limit the application of this method and its theoretical convergence guarantees. (2) There are some assumptions on the iterates $\varepsilon_k$ and $\delta_k$ in Theorem 2.4 and Theorem 2.5, but it is not clear whether these assumptions will ever be satisfied. Please refer to question (1) and (3) for details. (3) In numerical experiments, it would be better to report the time cost of different methods, including both the per iteration time cost and the total time cost.

Questions

(1) In Theorem 2.4, will the assumptions $\varepsilon_k = \sigma_{r+1} (X^{(k)})$, $\delta_k = \rho_{s+1}(X^{k})$, and $\varepsilon_k \leq \sigma_r(X_\star) / 48$ ever be satisfied? (2) The inequality at the end of page 6 only holds for certain $k$ satisfying the assumptions, so how do we arrive at the conclusion $X^{(k+l)} \to X_\star$ from such an inequality for one step? (3) In Theorem 2.5, how strong/restricted is the assumption that $\delta_k$ and $\varepsilon_k$ have limits, and the limits are positive?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

As far as I see, there is no potential negative societal impact of this work.

Addendum to rebuttal

Dear reviewer, Due to a technical issue, we could not submit a general rebuttal. The area chair kindly agreed to allow us to address your remaining question regarding the per-iteration and total time cost: In Appendix B of the submission, we discuss the per-iteration cost of the proposed IRLS algorithm on a basic level and mention that by applying the Sherman-Morrison-Woodbury formula, it is possible to rewrite the weighted least squares problem (18) such that the computational bottleneck is the inversion of an $O(r (n_1+n_2)) x O(r (n_1 + n_2))$, symmetric linear system. We note that in general, this can be done in a time complexity of $O(r^3 max(n_1,n_2)^3)$ using standard linear algebra. However, this system itself has a close-to-diagonal structure and is positive definite, so that high quality solutions could arguably found within few inner iterations (which would cost $(O(r (n_1 * n_2))$ each). If such a an implementation avenue is taken, the structure of the measurement operator might dominate the per-iteration cost of IRLS; for dense Gaussian measurements, the computation of one auxiliary matrix that is needed would cost $O(m n_1 n_2)$ flops. If rank-one or Fourier-type measurements are taken, this cost can significantly be reduced, see [24, Table 1 and Section 3] for an analogous discussion. We will include a more thorough discussion of the computational aspects into a final version of the manuscript, explaining also the details of our current Matlab implementation. Overall, we concede that additional work on the implementation will be needed to make the framework applicable to large-scale data such as in blind deconvolution and hyperspectral imaging problems. As for the total time cost of our method, we do not have a theoretical result due to the fact that we only analyze the convergence rate _close to the solution_, so the theory does not tell us how long it needs to takes to get into the local neighborhood starting from which we can quantify the complexity. However, we tried to illustrate the generic behavior of the algorithm in Figures 3 and Figures 6, which indicate that we find ourselves within a neighborhood within which quadratic convergence can be observed after only few iterations in many cases.

Addendum to rebuttal

Dear reviewer, Due to a technical issue, we could not submit a general rebuttal. The area chair kindly agreed to allow us to address your remaining question regarding the per-iteration and total time cost: We address this question in our "Addendum to rebuttal" to the review of Reviewer bSFz. Thank you for your understanding!