Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides a new computational framework of the matrix local low rank representation (MLLRR), namely Random Probing based submatrix Propagation (RPSP). RPSP is the first method capable of handling the general MLLRM problem. Specifically, RPSP utilizes a random projection and GPU-based computation of singular values for a large set of small matrices. It propagates the low rankness identified from small matrices to larger ones to identify local low rank submatrices of coherent patterns. On both synthetic and real-world experiments, RPSP outperforms all baseline methods on the LLR problems for data of different sparsity level and error distributions.
strength_and_weaknesses: Strength

1. RPSP is supported by rigorously derived mathematical theories, e.g. Lemma 1 and 2.

2. RPSP is the first method capable of handling the general MLLRM problem. 

3. In the experiments, RPSP outperforms all baseline methods. 

4. Experimental settings and parameter settings are clear. 

Weaknesses

1. Some mathematical expressions are difficult to understand. For examples, a few commas are missing in “k = 1...K” and other places. Corner signs almost always use superscripts, and lack the necessary explanation, e.g., does “N^R” denote N to the power of R? Does “10^-5 - 10^-2” means subtracting two numbers? And I cannot understand “for L^1 = 10^{1}12×2 matrices”. 

2. P is randomly generated, which is inefficient. 

3. As shown in Figure 4 and Table 1, even computing parallelly, RPSP has little advantage in running time. 

4. Lack of parameter sensitivity analysis, such as the experiments on the sensitivity of $\theta$. 


clarity,_quality,_novelty_and_reproducibility: 1. This paper is well organized. Experimental settings and parameter settings are clear. 

2. The MLLRR problem is an important problem in many areas, such as clustering and recommendation systems. 

3. I believe the experiments in this paper are reproducible, only if the GPU server and CPU server are available. 

summary_of_the_review: The authors develops  a sub-matrix propagation based approach to solve the fundamental mathematical problem of matrix local low rank representation.  This paper is well organized. Experimental settings and parameter settings are clear.  However, some details in the experiments need further clarification.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a method for local low-rank representation of matrices. The main idea is initially sample small size submatrices that progressively grow. At each step, a random projection-based method is used to evaluate the low-rankness of each matrix and assigning a score, which reflects the probability that a small-size matrix is contained in a larger one. These scores form a scoring matrix which determines the final local low-rank matrices that represent the input data matrix. The authors evaluate their method on simulated and real datasets such as Movielens and RNA sequencing data showing the promising performance of their method in terms of accuracy of the approximations and time efficiency of their method.
strength_and_weaknesses: Strengths:

- The paper deals with a challenging and interesting problem i.e., matrix local low-rank representation.  
- The authors provide a method, which is based on random projections and that helps towards deriving a more efficient method relative to other approaches.
- The authors provide numerous simulated and real-data experiments for evaluating their approach.

Weaknesses:
 - The main idea of the paper is the use of the random projection-based method for estimating the singular values of the submatrices in an efficient way. The authors also present Lemma 1 to support that singular value approximation method. However, they seem to ignore the literature and the methods already developed for randomized SVD [1,2]. The random projection-based method presented in Section 3.1, claimed by the authors as a novel contribution of the current work, relies on already existed work ([1,2]) that is not cited in the paper.
- Lemma 2 is poorly explained in the manuscript and hence is hard to grasp its contribution and impact of it in the paper. Can the authors use it in practice the result to get an upper bound on the number of submatrices they will need to consider?
- Section 3.2 is also poorly presented, and several steps of the methodology followed and given in Figure 3 are omitted or lack detailed explanation. For instance, it is not clear how the weighted sampling is done and how the local low-rank submatrices are determined using the scoring matrix.  Since these steps are critical to the method, further details should be provided in the main paper. Moreover, what is the computational complexity of the co-clustering algorithm that is used, and how that affects the efficiency of the whole approach?


Minor Comments

- Truncated SVD shouldn't be given as Definition 1.
- In the random projection-based algorithm, what is the sensitivity in the selection of the cut-off angle \theta? 

[1] Halko, Nathan, Per-Gunnar Martinsson, and Joel A. Tropp. "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions." SIAM review 53.2 (2011): 217-288.
[2] Martinsson, Per-Gunnar, and Joel Tropp. "Randomized numerical linear algebra: Foundations & algorithms." (2021).
clarity,_quality,_novelty_and_reproducibility: Parts of the paper are poorly written and it is hard to follow some of the ideas introduced. Namely, Section 3.2, which introduces the main methodology of the paper should be presented in more detail. Both the submatrix Propagation step and the low-rank prediction step  omit significant information that would allow the reader to better understand the proposed methodology.
summary_of_the_review: The authors present a methodology for matrix local low-rank representation. The main idea is to use a random projection-based method which allows them to efficiently derive low-rankness scores for progressively growing submatrices. These are used to derive the local low-rank representation. The author's main contribution relies on ideas of randomized linear algebra and prior work, which is not cited in the paper by the authors. Moreover, the main idea are poorly explained (see above) it is not clear to assess the significance of the results and that motivate the proposed methodology. 

-----------------------------------------
Post-Rebuttal Update:
I appreciate the authors' effort to respond to reviewers' comments and concerns, and I would like to thank them for that. However, this time I will not change my score. I think the paper's current version needs significant changes to meet the standards of ICLR. I encourage the authors to improve their manuscript based on the reviewers' suggestions and resubmit it to another conference.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The focus of this paper is on finding smaller-sized low-rank submatrices within a larger matrix. The main contribution of the paper is an algorithm that uses random projections along with a few other steps to find the low-rank submatrices. There is also a minor theoretical result in the paper that is asymptotic in nature.
strength_and_weaknesses: **Strengths**

- The algorithm, while mostly heuristic in nature, seems to be effective in finding the low-rank submatrices, at least on the matrices reported in the paper.
- There are numerical experiments that showcase the workings of the algorithm in comparison to other approaches in the literature.

**Weaknesses**

- The paper uses confusing and imprecise terminology, which makes it hard to pinpoint the main problem being studied in the paper. For example, the terminology of *low constant variation (LCV)* and *local linear low rank (LLR)* is never defined in a mathematically precise manner. The mathematical formulation in the paper never clarifies whether the indices $I_k \times J_k$ are meant to be disjoint or not. The concepts of *background noise*, *background error*, etc., are never defined concretely and it is also not clear if this is a requirement or not. In the absence of this mathematical rigor, one wonders if the problem is even a well posed one, and this is the biggest weakness of this paper.
- Lemma 1 seems to be gratuitous in nature. It is given under the assumption that $N^R \rightarrow \infty$, which makes it trivial, and it does not add anything to our understanding of the algorithm.
- Many of the ideas being presented in the paper, such as the use of random projections to approximate the minimum and maximum singular values of a matrix, are well known in the literature, but the paper does not make this clear.
clarity,_quality,_novelty_and_reproducibility: - The paper is not well written. It is difficult to understand in many places because of the writing style, grammatical errors, and confusing language.
- While the algorithm presented in the paper appears to be somewhat novel, many individual aspects of the algorithm are well known in the literature.
- The paper does not point to any publicly available repo, so the reproducibility of the paper cannot be evaluated.
summary_of_the_review: The results presented in the paper seem to be effective, but the paper needs a lot of work to make it publishable.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a method for progressively growing local low-rank representation of matrices using random projections. The evaluation shows that the method has promising accuracy and time efficiency. Reviewers agreed that although the technical content seems plausible, the paper in its current form is difficult to understand, the experimental methodology is unclear, and clear connections and attributions to relevant prior results in the literature are missing.
justification_for_why_not_higher_score: The reviewers all recommended rejection.
Decision: Reject