GENERALIZED MATRIX LOCAL LOW RANK REPRESENTATION BY RANDOM PROJECTION AND SUBMATRIX PROPAGATION
Authors: Pengtao Dang
Wennan Chang
Haiqi Zhu
Changlin Wan
Tong Zhao
Tingo Guo
Paul Salama
Sha Cao
Chi Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Matrix decomposition
Local Low Rank matrix detection
Representation learning
Subspace learning

Abstract: Detecting distinct submatrices of low rank property is a highly desirable matrix representation learning technique for the ease of data interpretation, called the matrix local low rank representation (MLLRR). Based on different mathematical assumptions of the local pattern, the MLLRR problem could be categorized into two sub-problems, namely local constant variation (LCV) and local linear low rank (LLR). Existing solutions on MLLRR only focused on the LCV problem, which misses a substantial amount of true and interesting patterns. In this work, we develop a novel matrix computational framework called RPSP (Random Probing based submatrix Propagation) that provides an effective solution for both of the LCV and LLR problems. RPSP detects local low rank patterns that grow from small submatrices of low rank property, which are determined by a random projection approach. RPSP is supported by theories of random projection. Experiments on synthetic data demonstrate that RPSP outperforms all state-of-the-art methods, with the capacity to robustly and correctly identify the low rank matrices under both LCV and LLR settings. On real-world datasets, RPSP also demonstrates its effectiveness in identifying interpretable local low rank matrices.


Under review as a conference paper at ICLR 2023
GENERALIZED MATRIX LOCAL Low RANK REPRESEN- TATION BY RANDOM PROJECTION AND SUBMATRIX PROPAGATION
Anonymous authors Paper under double-blind review
ABSTRACT
Detecting distinct submatrices of low rank property is highly desirable matrix representation learning technique for the ease of data interpretation, called the matrix local low rank representation (MLLRR). Based on different mathematical assumptions of the local pattern, the MLLRR problem could be categorized into two sub-problems, namely local constant variation (LCV) and local linear low rank (LLR). Existing solutions MILRR only focused on the LCV problem, which misses substantial amount true and interesting patterns. In this work, we develop novel matrix computational framework called RPSP (Random Probing based submatrix Propagation) that provides an effective solution for both the LCV and LLR problems. RPSP detects local low rank patterns that grow from small submatrices of low rank property, which are determined by a random projection approach. RPSP is supported by theories of random projection. Experiments on synthetic data demonstrate that RPSP outperforms all state-of-the-arr methods, with the capacity to robustly and correctly identify the low rank matrices under both LCV and LLR settings. On real-world datasets, RPSP also demonstrates its effectiveness identifying interpretable local low rank matrices.
INTRODUCTION
Matrix approximation has found wide-range utilities in recommendation systems, computer vision and text mining. Traditional matrix low rank approximation methods, such as truncated singular value decomposition (SVD) and rank minimization, assumes that the observed matrix has global low-rank, indicating that the low rank components are dense. This becomes challenging in the phase of data interpretation. In real world data, both features and incidences may form sparse subspace structures. As illustrated in Fig 1, matrix can be generated as the sum of a series of local low rank matrices, each consists of a sparse of features and incidences. One example of such 'locality" property is the purchase history data, where a subset of items were purchased under a common reason by subset customers, while neither the items bought together or the users sharing common purchase reason is known Cheng et al. (2014). Similarly, in biological single cell ANA-sequencing data, a subgroup genes may be regulated by an unknown signal that activated only subset of cells, which forms local low rank gene co-regulation module Xia et al. (2017); Wan et al. (2019a); Chang et al. (2020). In addition, shapes, numbers and words in imaging data are also local low rank Lee et al. (2016). In these situations, Matrix Local Low Rank Representation (MLLRR) is more advantagcous with its locality assumptions to uncover more interpretable patterns hidden in the data.
Original Data
Position
Signal
Figure One example of the Matrix Local Low Rank Representation (MLLRR) Problem.

---

Under review as a conference paper at ICLR 2023
For input matrix X E RMX,, MLLRR aims to identify submatrices X1exJ2; k I...,, each with a distinct low rank structure, where Ig and J/ represents row and column indices. The total number of possible Ia XJ& combinations is 2 making the MLLRR problem NP-hard /tor//tockmmyer (1975). Existing methods for MI.RRR fall into three categories: (1) co-clustering approaches that
identify submatrices with distinct mean comparing background Wan et al. (20T9b); [Banerjee et al.)
(2007); (2) Sparse matrix decomposition based methods that penalize the number of non-zero entries
in the factor/singular matrices Yang et al. (2014); [Shen & Huang (2008); x Lee et al. (20T0); (Stll et al. (201T); Witten et al. (2009); Hochreiter et al. (2010); and (3) Anchor-based methods that first pinpoint local regions using certain primitive similarity measure, and further conduct a low rank fitting to each anchored region [ee et al. (2016). Noted, all these methods rely on the assumption that the low rank submatrix has a distinctly spiked mean compared to the background Yang et al. (2014). Identification of submatrices with a more general definition of low rank property remain unsolved, including: (1) the submatrices having a low rank and a similar mean compared to the background, (2) the background noise matrix having heterogencous and even contaminated distributions, and (3) the submatrices is of a small size or has heterogeneous error distributions.
In this study, re-visit the tasks of MLLRR from the perspective of random projection and developed a new framework, namely RPSP (Random Probing-bate based Sub-matrix Propagation). RPSP first evaluates low rankness of a large set of randomly sampled small submatrices, and gradually grow these low rank submatrices using a propagation strategy. RPSP adopts a random projection approach to approximate the singular values of submatrices that drastically improved the computational efficiency compared to the conventional QR decomposition based computation.
We systematically benchmarked RPSP with state-of-the-arts (SOTA) methods on comprehensively simulated data and two real-world datasets. RPSP outperformed all SOTA methods on different senarios. RPSP is shown have the unique capability to handle heteroscedastic error distributions, and distinguish a true local low matrix from background noise with or without spiked mean struc- ture. Application of RPSP on real world datasets demonstrated its capability in detecting context meaningful local low rank matrices.
The key contributions of this work include:
(1) RPSP is the first general solution for the LCV and unsolved LLR problems: Compared to existing methods, RPSP is the only method that can robustly solve the MILRR problem when (i) the patterns small, (ii) the mean of patterns is not necessarily distinct compared to background, (iii) the background error is non-Gan aa--aassian or heterogeneous, and (iv) there are a large of low rank submatrices of different size and ranks.
(2) A new perspective in analyzing and embedding local low rankness: We developed new framework for computing and propagating local low rankness of submatrices by estimating singular values of randomly sampled small submatrices and propagating small low rank submatrices to gradually grow into larger ones. This framework directly computes the probability of local low rankness, which also serves an interpretable embedding of matrix data.
(3) A theoretical framework is developed from mathematical theories of random projection that support: (i) the identifiability of local low rankness, (ii) bound of sensitivity and specificity, and (iii) impact of errors and pattern sizes with respect to the setting of hyperparameters of RPSP.
(4) An efficient computation of singular values: A random projection and paraliel computing- based method on GPU was developed to drastically increase the computation efficiency of singular values for large set of small matrices.
PRELIMINARIES
2.1 NOTATIONS AND MATHEMATICAL BACKGROUNDS
We denote a matrix X of M rows and N columns as XMNN, and its -th entry as X We use Ts C (1, (1,..., M) and Js C (1,.... N) to denote row and column indices, and X XJxxJ, means a submatrix indexed by I x Jr. ||x |1, || ||X||. denote element-wise C-1, L-2, and nuclear norms of a matrix, here nuclear norm is the sum of all singular values X. For Z MMN we use Rank(Z) to denote the rank of the matrix. Rank(Z) = if and only if Z = UVT, where U E V'RMX Mx and V E R Xx are two orthogonal rank-r matrices. To say that has a low rank property, we mean < mán (an N). Intuitively, random matrix will have rank of min(M.N) The low rank property of a matrix added by background noise is commonly characterized by truncated SVD, as defined below.
2

---

Under review as a conference paper at ICLR 2023
Definition 1. Truncated SVD. Let ZMxN = UEVT(M 2 N) be the singular value decomposition
(SVD) of Z, where UMN and V are left and right singular vector matrices, Σ X N is a diagonal matrix of singular values. Define diagonal matrix g such that 2n//7 Ea; i S
- = 0, > r, ie.. the top singular values. The truncated SVD of Z of rank r is defined as tSVD" (2) = UT By its definition, the numerical rank of Z is r if and only if Z = UT
When Z is added by noise, we utilize optimal VSV to characterize the low rank property of Z, which has been widely utilized in low rank representation of a matrix with errors Owen et al. (2009): : Wold 1978). Specifically, the optimal LSVD of Z is defined as 1.V 1.SVD" (Z) = [ VV" where r" is the smallest number such that E == Z UΣ(">²" that forms an independent and identically distributed noise matrix or any predefined noise structure. We call r* as the estimated rank of z. Noted, estimating the exact rank r' requires additional assumption of noise, which is not the
primary focus of this work. Nonetheless, a matrix is low rank if and only if Σ E. substantially larger compared to a random noise matrix.
(vk I r*) is
[2]|.
2.2 PROBLEM STATEMENT
Definition 2. Matrix Local Low Rank Representation (MLLRR). For given matrix XMxN MILER identifies K low rank submatrices X₁ == XIxxJ,, Ja C (1...M,, Ja C (1..NN),
1, K, s.t. LSVD'
U. Un E fRmxxra, Va E Rnaxre, F& & min(m,, ng), i.e., Xx are low rank submatrices added with error. Here me and nig denote the cardinality of I5 and Jn.
The MILLR problem could be categorized into two sub-problems based the low-rank property: (i) LCV (Local Constant Variation) considers submatrices with spiked expected means (E) compared to the background. i.e. E(Xig) = ug, V(i,j) E 14 x Jr, B(X,,) = uo, ji. & {1u J= (ii) LLR (Local Low Rank) considers submatrices whose optimal tSVD are of a low rank rk, i.e. ISVD (X1,xx) = Uz Zf V.T where S Tkk < min(m,, nz)-
Noted, the LCV problem is a special case of LLR. We separate the two problems because most existing approaches only solve the LCV problem. Let Eis := Xx +SV (Xx))) be the background noise of the kth submatrix. Importantly, real world data is often noisy and heteroscedastic, meaning (1) the distribution across different Eg may not be identical; (2) for (i. & (I& x J+) Xi, may not be identically distributed; and (3) certain entries in X5 may be outliers that could corrupt its low rank structure. Of note, in this study, we do not restrict the form of the background noise distribution.
2.3 RELATED WORKS
Currently, there exits three types of methods that can solve the MLLRR problem, namely co- co-clustering, sparse matrix decomposition, and anchor- anchor-based approaches. The main goal of co-clustering matrix partition such that the intra-co-cluster distance could be minimized, where the distance measure defined as the Kullback-Leible divergence Bregman co-clustering [Banereee et al. (2007), and Fuclidean distance in the plaid model Lazzeroni & Owen (2002). For matrix decomposition based methods, they identify local low rank matrices by imposing sparsity constraints to the factor or singular matrices U, V WWitten et al. (2009); Yang et al. (0014); Lee et al. (2010); Shen & Huang (2008); Sill et al. 2011). For anchor- based methods, Lee et al. proposed the LLORMA method by using prior knowledge to select anchors of local low rank patterns and their nearby points with smooth kernel function Lee et al. (2016); Chen et al. proposed the WEMAREC method that builds upon the submatrices identified by co-clustering methods Chen et al. (2015). More details on the existing method formulations were provided in APPENDIX. Among the three types of methods, co-clustering only solves the LCV problem. Although both matrix decomposition and anchor-based methods focus on detecting LLR submatrices, only those submatrices with a distinct spiked mean could be detected. In other words, only the L.L.R submatrices having the LCV property could be detected. In addition, sparse matrix decomposition tends to detect large submatrix that may explain better the variance of the whole matrix, while sacrificing the locality of the low rankness Yang et al.) (2014); Shen & Huang 2008). and the high computational cost of anchor-based methods are not scalable to large matrix Lee et al. (0016): Chen et al. (011)). And none of the existing methods is capable of handling outliers or heteroscedastic errors. In summary, there is lack of effective and scalable solution for the general MLLRR problem, especially when the mean of the target submatrix is not different from the background and the data contains outliers and/or heteroscedastic errors.
find
3

---

Under review as a conference paper at ICLR 2023
3 RPSP AND ITS MATHEMATICAL BASIS
The biggest challenge with local low rank submatrix detection lies in that neither the row column indices of the submatrix is known. As given in Definition 2, the low rankness property a submatrix is evaluated through the computation of its singular values, which apparently can't 't be evaluated until the submatrix has been presented. However, it is computationally impossible to go through all the submatrices of an input matrix. RPSP grows submatrix of low rank from smaller ones, which utilizes two facts. Firstly, for a low rank matrix X XMNN of rank r < min((M, N). the self consistency property suggests that any Mo No submatrix (Mo. No 2 r) randomly sample from X is most likely to have rank of r (Lemma in Owen et al. (2009).. Secondly, for a given matrix, the total number of square submatrices of dimension Mo grows exponentially with Mg. The first fact indicates that, any submatrix of low rank is collage complete coverage of its own (smaller) submatrices, which are also of low rank. The second fact indicates that the only way for us to grow local low rank submatrix is to start from the much smaller submatrices. In fact, for My as small as 2, it is computationally feasible for us to obtain a full collection of Mo x M, submatrices that could densely cover X M By teasing out all the Mo Mo submatrices of low rank, could then gradually build them up into larger low rank submatrices. The evaluation of the low rankness for large number of submatrices now becomes computationally expensive. In RPSP, our biggest contribution is that we have developed a singular value approximation method using random project efficiently evaluate the low rankness of any given submatrix, making it possible for us reconstruct a low rank submatrix from its parts.
(a)
(0)
14
101
Figure 2: Mathematical considerations of random projection prodeetion-based singular value computation.
3.1 EFFICIENT COMPUTATION OF SINGULAR VALUES FOR A LARGE SET OF SMALL MATRICES
Conventionally, singular values are computed by QR decomposition of O(n)) complexity. In this study, we developed an alternative approach to drastically increase the efficiency of computing singular values for a large amount of small matrices from the perspective of random projection. Without loss of generality, we illustrate our mathematical bases and the computation of singular values on square matrices. In Lemma 1, we first proved that the singular values of X can be estimated via simple operations against set of randomly sampled unit vectors, including inner products, sum of squares, and max pooling, which can be efficiently computed on GPU. Lemma 2 derived from the theories in Random Covering of Unit R-Sphere suggests the minimal requirement for densely covering a Unit R-dimensional Sphere. It estimates the number of random unit vectors that are needed to ensure that for any vector in IR" R there almost surely exists at least one random unit vector, whose cosine similarity to the vector is larger than cos O.
Lemma 1. For a given dimension R, denote R R as an input matrix and P E R Rx N matrix of R randomly generated unit vectors in IR., R Y XPP denotes a random projection of X, then lim max
as
VER YG = OR. here a VE = σs and lim min # 15/5NR
N = ISJSNR
V
and an are the largest and smallest singular values of X. Denote P(t) = arg max P.,
lim N 00 P... PP(())))
max
R Y3 02 02. where Sp(P denotes the null (or complemented) space E
arg max of the linear space spanned by P(1). Similarly, define P(r) P.)ESS P(--)))
VE Yz.
max NR E Pa...... P(-
lim
Σ E Y or, for r E 3, .... R 1.
4

---

Under review as a conference paper at ICLR 2023
Lemma 2. The minimum number of caps of half angle 9 required to cover the unit Euclidean R-sphere is called the Random Covering of the Unit R - Sphere. Then
NR R, =0)==epp exp( fc( (n()))
where CR - > 0 as R + 0o and fo(0)= -log sin A. Here No O) is the minimum number and half angle 0. This means, when is large enough, if
of caps with the given dimension we randomly choose exp(- - -RlogsinO + o( [t)) caps, then the area of the uncovered surface of the R-sphere will be almost negligible.
The proof of Lemma 1 is given in APPENDIX and the Lemma 2 was proven as Corollary in the section I/ of Wyner (1967). Lemma and together suggest that for given matrix and the level of error to be tolerated, its singular values could be estimated by simple operations against set of randomly generated unit vectors, which form the mathematical bases of Algorithm 1: Singular Value Approximation. Its input includes matrix X (Fig 2a) and set of randomly generated unit vectors P (Fig 2b), whose cardinality bounded by Lemma 2. It projects X onto P and iteratively estimates singular values and the null space of the approximated left singular vectors (Fig 2c).
Algorithm 1: Singular Value Approximation (Based on Random Projection)
Inputs: X N randomly generated unit vectors denoted as P E R cutoff Outputs: Estimated singular values 01 02: Rn
Singular Value Approximation X, P.O): Y XP
Generate vector E, E, E3 + V E Y
NR)
σ1 + max
on f min [Fy]1 NRJ
P()) = arg max E, Prullss t P3 are columns of P}
P.,
for I,.., do
Ppuulsy t- (PjIP, E Prrnte max P3. P(y)) cos Pj P(,))} < cos( 0r+1 + max (E, the corresponding P, of Ej E Prillsap
P(r+1)* + arg max El E pnullspp
P3
end
return
{01, 02, ..., RR}
In Algorithm 1, P(r) and Paullsp are estimated rth left singular vector and the null space of the linear space spanned by the first r left singular vectors, respectively, As randomly generated vectors cannot be stringently orthogonal, 0 is a hyper-parameter that determines the randomly generated the null space of P(r)- Noted, the null space of the linear space spanned by each P3
vectors that does not rely on X that can be computed before the random projection. Thus, the random projection and iterative computing of o, and P(r)) only involve inner product, max, and sum of squares, which can be efficiently and parallelly computed on GPU for a very large set of small matrices.
We have evaluated the computational efficiency and accuracy of Algorithm 1 versus conventional QR decomposition-bant based SVD on both GPU and CPU servers (see more details in APPENDIX). We tested the two methods 50 times on 10 106. 107 and 108 2 10 4 4, and 10 x 8 matrices. The averaged normalized root mean squared error between estimated and true singular values is 0.07, We observed that Algorithm 1 used 10- 10-2 seconds, which consistently about 10 faster than QR decomposition based SVD. The max pooling step can be further optimized by first clustering the random unit vectors into groups of high cosine similarities (Fig 2d), as detailed in APPENDIX.
3.2 THE RPSP FRAMEWORK
Algorithm 2 and Fig 3 illustrate the main framework of RPSP. The inputs of RPSP include matrix X M and cuper-parameters. The output are identified local low rank matrices, denoted as {X1, J2 },K
1.... K. The initialization step of RPSP generates random unit vectors for estimating singular values small matrices. Specifically, N, random vectors of length 2', denoted as Pr. 1 I...7 will be generated, where T is the number of layers for submatrices propagation.
5

---

Under review as a conference paper at ICLR 2023
[ii) Singular Value
(1)
Singular Value
p1
Approvimation
pc
Approximation
E
g
Randomi 2X2
Sub Sub-MMttrix
(iv] Local Low Rank
X MMN
Sampling
Propagation
C-1 layers
Sub-Matrix Propagation
X M
Prediction
Figure 3: The framework of the RPSP algorithm.
RPSP first randomly samples L1 2 x 2 submatrices from X, whose singular values are estimated by Algorithm 1 against P1. as described in 3.1. Noted, 2 x 2 the smallest unit submatrix that possess a low rank structure. Our evaluation of Algorithm 1 suggests that the computation for TP] characterizes the low rank property of 2 x 2 matrix P, where and ||]|| denote the first singular value and nuclear norm of P. The low rank property of the 2 submatrices is further propagated by a weighted sampling to generate L2 4 x 4 submatrices. Specifically, a pair of none overlapped 2 x 2 matrices were randomly sampled by a probability weighted by the average of their ![! values. The row and column induces of the two samples matrices form a new x 4 submatrix. The singular values of the x 4 submatrices will be estimated by random projection and orthogonal pooling against Pz. This procedure will be iteratively conducted T times, by which Lt 2d x submatrices will be randomly sampled weighted by the low rankness propagated through the T layers, whose singular values will be estimated. For each t = 1, ..... T. RPSP also computes M x N scoring matrix St, in which Si, stores the frequency of observing large value of ||P||| among all the sampled 2 x 2 submatrices that hits Xij- ST can be viewed as an approximation of the probability that X.j contained by LLR submatrix with size of 2 x 2 or larger. The local low rank submatrices in X can be further identified by co-clustering over ST. RPSP (Algorithm 2) consists the following sub algorithms:
T,- 12 2 matrices uses less than 10s. The value
21
(i) Singular Value Approximation (Algorithm 1) computes singular values for the 2 x 2' subma- trices, as described in 3.1.
(ii) submatrix Propagation generate 26+1 2 submatrices by randomly sample pairs of non- overlapped 2 x 2' submatrices with probability weighted by the average of the low rankness score. This approach enable the propagation of the low rankness of two small submatrices to a larger one the two small submatrices truly hit one local low rank submatrix. (Detailed in APPENDIX) (iii) Local Low Rank Prediction reconstructs the local low rank matrices in X based on the scoring matrix S (Detailed in APPENDIX).
In the Algorithm 2, P. denote the sets of randomly generated unit vectors; R, denote the sets of the
2 x 2 submatrices randomly sampled (1 1) weighted sampled (1 = 2, T) by submatrix Propagation; Ro[i] denotes the jth submatrix in R; Et,xxL= store the estimated singular values; Scnk is a vector stores the top singular value divided by the nuclear norm of each 2 x 2" submatrix and S denotes the scoring matrix, where ST,, is the frequency of observing Low Score > C' for all the submatrices that contains Xij. Noted, the super-parameters T and L, can be easily determined based on the computational capability while C and N, can be determined based on the level of errors can be tolerated (see details in APPENDIX).
4 EXPERIMENTS ON SYNTHETIC DATA We evaluated the overall performance and computational cost of RPSP on different scenarios of MLLRR problem compared with SOTA methods on a comprehensive setup of synthetic datasets.
4.1 EXPERIMENTAL. SETUP SETUP
We simulate X E RMX as X - X* + E. Here, entries in X is padded by zero except for those indexed by Ia and Jg. corresponding to local low rank submatrix with my rows and n& columns. E is background noise simulated by E ~ NO, ag * sd), Vi E Ik.j E Jj: and the rest of the entries in E follows ((0 sd). In evaluating the algorithm's 's scalability, we allow M and N to have three different values. Otherwise, we let M = N = 1000. To simulate X Ig Ju we first simulated Y& as Yv V.V. where Up mm X and V E X and entries in Uk, Va all follow UO0, 1). Then X J is simulated as Vt- Yx + p4k Here, Yū denotes the element- wise mean

---

Under review as a conference paper at ICLR 2023
Algorithm 2: RPSP
Inputs: X MXN, peper--arameterss T, Nt. Lr. C,t = I.... Outputs: The indices set (I J), where I E JR E J, X1xx, is a local low rank matrix. RPSP(X, X,T, T, NN, Le, C):
for in I....TT do
1 P. + (N, randomly generated unit vectors of length 2')
end
R1 4- [L1 x 2 submatrices randomly sampled from X)
F1,2xL1 <- Singular Value Approximation(Ra Pt)
for in 2, do
R₂ < submatrix Propagation( (X, R,-1, L2)
F.2
Singular Value ep P.)
end
for in I..... LT do Low R +- ET E.
FT,
end
for i in I...,,M MMM... do
for in I....,N do ig + frequency of Low Score [A] C' for all [k] contains Xij
end
end
I +- Local Low Rank Prediction(S*
return I J
of matrix Ys. and hence μı mimics the overall mean of the k-th pattern matrix, and ag mimics the relative noise level of the local low rank matrix to the overall background noise matrix. In total, we obtained 284 different simulation scenarios, each has 5 repetitions, which include:
(1) Perturbed pattern mean: pattern mean H4: 3gg sd, where 3g is sequence from to 3 with
step size 0.1; relative noise level Og {0, 0.1 pattern size my n2g. {000,500)
(2) Perturbed background error: pattern mean μl = 3g sd, where 3g = {0, 0.13: relative noise
level ag is sequence from 0 to 3 with step size 0.1; pattern size m& n& {200, 500}.
(3) Perturbed pattern size: pattern mean μt = 3g * sd, where 3g = {0, 0.13: relative noise level
O% (0, 0.1); pattern size my n4 is sequence from 100 to 500 with step size of 20.
We evaluated the method performance of RPSP and selected SOTA methods on these synthetic datasets, based how well the identified patterns hit the true ones, and avoid the background noise. We label the entries hitting true patterns as "positive" and the rest as "negative", and the True Positive (TP), False Negative (FP), False Positive (FP), and True Negative (TN) occurrences are defined the number of "positive" entries that are identified as pattern (TP) or background (FP), or the number of "negative" entries that are identified as pattern (FP) or background (TN). The overall prediction TP+NN
accuracy is defined as TP4TN+FP4FN
4.2 PERFORMANCE EVALUATION OF RPSP
We benchmarked RPSP with five SOTA methods, namely Bregman co-clustering (CC) Banerjee et al. (2007) and Plaid Lazzeroni & Owen 2002). two sparse matrix decomposition methods (SSVD Yang et al. (014) and SPCA Zou et al. (2006)), and one anchor based method I.IORMA| Lee et al. (2016). Detailed parameter setting RPSP and other methods are provided in APPENDIX.
Accuracy in solving the LCV and LLR problems. Fig 4a-c illustrated the accuracy (y-axis) of RPSP (red) and other methods for solving the LCV and LLR problem in different scenarios. Overall, RPSP achieved higher than 0.8 accuracy under most settings, which is consistently higher than baseline methods. On the dense data, SPCA failed to identify any pattern while CC detects the whole matrix pattern, hence these two methods were excluded from further analysis. RPSP is the only method that can identify local low rank pattern when its mean is close to the background mean (Fig 4a), i.e., the LRR problem without the LCV property. As expected, observed the prediction
7

---

Under review as a conference paper at ICLR 2023
Size: 200, Error: 0ld)
Size: 200, Eroon 0. (idi
Size: 500, Enoo:: Olse)
Size: 500, Erron: 0. lidi
Mean Test Accuracy
2-
0453
1.250
2054
046c)
1,250
206d
2
n43e
126cl
2.Rodd)
Mean Stift
Mean Stift
Mevn Statt
Mean Shift
Size: 200, Mear: O(sd)
Size: 200, Mean: (sd()))
Size: 500, Mean: Dlsd)
Size: 500, Mear: 0. 0.T
Error Test Accuracy
84
2000
B460)
1
2000
1.244
70bd
Eroo Stdle
Inor Soele
Emar Scale
EnorScel-
8
Enror: (sd],,, Mean: O(sd)
Erron: n.5(s,), Mear: O(od)
Erron 0,11sl), Mean: (.1(sd)
0.5isd Mears O. (ssd)
Size Test
Accuracy
100
200
300
400
100
200
300
400
500
100
200
30C
400
550
100
.00
2003
500
len:
Two Patterss Accuracy
(44)
Four Patterns Accuracy
1891
Time Comparison
(60)
Score
2.51
0.20
0.22
24
06
DAA
04
LIK
2013
UI2
181181
2nd61
hole
7
48-L81
PlAto
usbet 100dh 20000
RPSP
LLORMA
ssvd
spca
plaid
Figure 4: Benchmark of RPSP on Synthetic Data.
accuracy of the baseline methods to increase the mean difference becomes larger (Fig 4a). and all methods to have decreased performance with the increase of the noise level (Fig 4b). RPSP and ILORMAA more robust to high noise level compared to SSVD and Plaid. The size test suggested that RPSP can accurately identify the pattern when its size even smaller than 100 x 100 a 1000 1000 matrix (Fig 4c). When the pattern size increases, the prediction accuracy of RPSP and LLORMA also increase, but not SSVD or Plaid. An explanation is that a larger pattern is easier to be hit by the randomly sampled submatrices in RPSP the anchoring in LLORMA, while SSVD and Plaid rely on the pattern sparsity assumption and are less sensitive to large patterns.
Power in detecting multiple patterns and the submatrices different ranks. Where there exists more than local rank-1 1 sub matrices, RPSP again achieved high performance (Fig 4d1-2). The way RPSP detects local low rank matrices from the scoring matrices, which less impacted by the number of patterns. It is noteworthy that we focus on the LLR problem in dense matrix, while LLORMA and Plaid are more efficient on the LCV problem in a sparse matrix. On the dense matrix, all the baseline methods failed to identify the LLR pattern when the mean difference of the pattern and the background is low. We also evaluated RPSP on identifying LLR patterns of different dimensions (Fig 3d4). Our results demonstrated that RPSP has a high robustness in detecting patterns of different dimensions. Noted, the specificity of RPSP is always bounded by a, where a is the probability of presence of local low rank matrix in noise matrix.
Running time. We evaluated the time consumption of the methods on dense matrices three sizes, M N 10a 10 10a (Fig 3d3). The running time of RPSP, Plaid and LLORMA a similar level. Detailed experimental results and parameters of the GPU and CPU server for the experiment are provided in APPENDIX.
8

---

Under review as a conference paper at ICLR 2023
Table 1: Experiment real-world data.
GSE165322
Tow Rankress
Siew
CR
Timejo]
Tow Earictess
Sinw
CR
Timelal
RPSP
0.82
0.76
0.73
0.8
0.72
0.76
1.70E-00
1.90E+08
2.50E-03
7.005-02
7,005-02
2,50E-03
0.1
$7.00
0.44
0.7
0.43
0.5
0.47
0.45
6.00E-04
1.30E-05
4,50E +0
1.00E+05
8.50E+04
4,00E404
0.00
500.5
LLORMA
2,50E+03
2.90F-01
2.405-03
2.505-03
0.05
0.39
0.38
1,505404
1:505+04
1.501+04
0.02
SSVD
0.50
0.5
0.5
0.5
0.49
0.5
2,308+08
2.505:03
2.50E-03
-525-03
2,50E-03
2.308+03
0.06
1.37
0.41
0.24
0.
0.25
0.19
1.50E
1,50E
104
1,50E
1.50E
404
1.503+404
1.000:444
0.00
49.59
SPC4
0.48
0.48
0.48
0.48
0.48
0.48
2.505-03
7.007+01
2. -000-000
2.505-03
7/10F-01
2.525-03
0.05
0.15
0
0
0
0
108
1.0
198
790
198
190
2.00E 044
3.55
PLAID
NA
NA
0.31
NA
8.10E103
NA
1.00E
182.84
N4
NA
NA
NA
NA
6.00
NA
NA
NA
NA
0.18
0.28
NA
M
N4
NA
4.305405
NA
N6
NA
N4
0.05
EXPERIMENTS ON REAL-WORLD DATA
We benchmarked RPSP on two real-world datasets of different density rates (proportion of non-zero entities in the overall input matrix), error distributions, and local low rank patterns, namely (1) the MovieLenns data and (2) single cell RNA-seq data. Details of data processing and algorithm settings are given in APPENDIX. Four metrics were utilized to evaluate the performance of each method, namely (1) the Low Rankness, calculated as the averaged TPPI identified submatrices P, (3) the total Coverage Rate(CR), defined as the total number of entries in the top-k patterns divided by the size of the input matrix, and (4) the Running Time. In addition. context specific meaning was evaluated based on prior knowledge.
a and (2) the averaged Size of the
Application to Movrielens data. MovieLens 25M data is a common benchmark dataset. It contains the ratings of 62,000 movies by 162,000 users provided by CroupLen/Harperr & Konstan (015)) We selected the top 600 active users(rows) and the 600 most rated movies(columns)) reaching a density rate of 20.0%. This is relatively sparse dataset. Indeed, on sparse data, all baseline methods tend to identify LCV submatrices, but still RPSP is more favorable than others in terms of the low rankness, coverage rate. As shown in Table 1, the low rankness of the top six significant local low rank matrices identified by RPSP is consistently higher (~0.75) than the ones detected by baseline methods (~00.5). While the patterns detected by RPSP is of smaller sizes, their coverage rate is higher than LLORMA, SSVD and SPCA because RPSP tends to detect non-overlapped patterns while the top patterns identified by baseline methods are heavily overlapped.
Application to single cell (sc) RNA-seq data. The local low rank submatrices in scRNA-seu corre- spond to sub- coa--opulation of cells with distinct functions and the error distribution is heteroscedastic and non-Gaussiae Hou et al. (2020) Wan et al. (2019)). We applied RPSP and baseline methods on head and neck cancer scRNA-seq data, namely GSE103322 Puram et al. (2017). Here we removed certain genes and cells with low expression, bringing the density rates to 75.71%. As shown in Table 1, the low rankness, size and coverage rate of the top patterns identified by RPSP are consistently higher than the ones detected by baseline methods. We conducted enrichment analysis of the gene features in each detected submatrix examine their interpretability [Hang et al. (2007). We found three local low rank matrices identified by RPSP that significantly enrich biological functions including cell metabolism, cell proliferation, and antigen presentation.
In summary, RPSP outperforms all baseline methods in detecting local low rank matrices on the real-world datasets, in terms of the low rankness, size, coverage rate, and contextual interpretability of detected local low rank patterns. The running time of RPSP is at similar level of baseline methods.
CONCLUSION
In this work, we provided a new computational framework, namely RPSP, detect local low rank matrices. RPSP is supported by rigorously derived mathematical theories. While existing methods mainly focused on one sub-problem of MILLR,, our developed RPSP is the first method capable of handling the general MILRMM problem. RPSP utilizes an efficient 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, we demonstrated that RPSP outperforms all bascline methods on the LLR problems for data of different sparsity level and error distributions. Particularly, RPSP could detect low rank submatrices even when its mean structure is not distinguishable from the background, when the error distribution is heteroscedastic.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Arindam Banerjee, Inderjit Dhillon, Joydeep Ghosh, Srujana Merugu, and Dharmendra S Modha. A generalized maximum entropy approach to bregman co-clustering and matrix approximation. Journal of Machine Learning Research, (AAug):111--1988) 2007.
Wennan Chang, Changlin Wan, Yong Zang, Chi Zhang, and Sha Cao. Supervised clustering of high dimensional data using regularized mixture modeling. arXiv preprint arXiv:2007.097200 2020.
Chao Chen, Dongsheng Li, Yingying Zhao, Qin Lv, and Li Shang. Wemaree: Accurate and scalable recommendation through weighted and ensemble matrix approximation. Proceedings of the 38th ACM SIGIR, pp. 303-312, 2015.
Yao Cheng, Liang Yin, and Yong Yu. Lorslim: low rank sparse linear methods for top-n recommen- dations. In 2014 IEEE International Conference on Data Mining, pp. 90-99. IEFF, 2014.
Inderjit S Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 269-274, 2001.
N Benjamin Erichson, Peng Zheng, Krithika Manohar, Steven L Brunton, J Nathan Kutz, and Aleksandr Y Aravkin. Sparse principal component analysis via variable projection. SIAM Journal on Applied Mathematics, 80(2):97--102.. 2020.
Yuhan Hao, Stephanie Hao, Erica Andersen-Nissen, William M. Mauck III, Shiwei Zheng, Andrew Butler, Maddic J. Lee. Aaron J. Wilk, Charlotte Darby, Michael Zagar, Paul Hoffman, Marlon Stoeckius, Efthymia Papalexi, Eleni Mimitou, Jaison Jain, Avi Srivastava, Tim Stuart, Lamar B. Fleming, Bertrand Yeung, Angela J. Rogers, Juliana M. McElrath, Catherine A. Blish, Raphael Gottardo, Peter Smibert, and Rahul Satija. Integrated analysis of multimodal single-cell data. Cell, 2021, doi: 10. (0.1016/j.cell.222) 202...0.00....... URL http:::p:///// htt.///oii.c org 1016 22021. 04.0444.4 048
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4), 2015.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane. Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchan Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, 355.0 September 2020. doi: 1000:6644115--0002266--22-2 URL /ttttps://do..rree
Kevin Sheppard, Tyler Reddy,
/41586 020 2 2
Sepp Hochreiter, Ulrich Bodenhofer, Martin Heusel, Andreas Mayr, Andreas Mitterecker, Adetayo Kasim, Tatsiana Khamiakova, Suzy Van Sanden, Dan Lin, Willem Talloen, et al. Fabia: factor analysis for bicluster acquisition. Bioinformatics,
2010
Wenpin Hou, Zhicheng Ji, Hongkai Ji, and Stephanie Hicks. A systematic evaluation of single-cell maäsequencing imputation methods. bioRxiv, 2020.
Da Wei Huang, Brad T Sherman, Qina Tan, Joseph Kir, David Liu, David Bryant, Yongjian Guo, Robert Stephens, Michael W Baseler, H Clifford Lane, et al. David bioinformatics resources: expanded annotation database and novel algorithms to better extract biology from large gene lists. 169-6691111 Nucleic acids research, 35(suppl_ 2): 269W169-VV 1119--175,... 175,,
2007.
Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A llym-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, pp. 1-6, 2015.
Laura Lazzeroni and Art Owen. Plaid models for gene expression data. Statistica sinica, pp. 61-86. 2002.
Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer, and Samy Bengio. Llorma: Local low-rank matrix approximation. JMLR, 17:442-465 2016.
10

---

Under review as a conference paper at ICLR 2023
Mihee Lee, Haipeng Shen, Jianhua Z Huang, and JS Marron. Biclustering via sparse singular value decomposition. Biometrics, 66(4):1087-1095, 2010.
Art B Owen, Patrick O Perry, et al. Bi-cross-validation of the svd and the nonnegative matrix factorization. The annals of applied statistics, 3(2), 2009.
The pandas development team. pandas-dew/pandas: Pandas, February 2020. URL https://doi
org/10. 0t11:00521///eeceeca wwtod//eezoooooom 3509113
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vitito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances
Neural Information Processing Systems 32, pp. cc/ppprr/ 9015 pattpchttochaa-t in-immeaatiiveee style hwghhhhghhhhhheeeeeeee perhhhrrroorreeeee deweemaaaneeeeee--eeee pdf
8024-8035, Curran Associates, Inc., 2019, URL
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research,
12:2825-288 2830, 2011.
Sidharth V Puram, Itay Tirosh, Anuraag S Parikh, Anoop P Patel, et al. Single-cell transcriptomic analysis of primary and metastatic tumor ecosystems in head and neck cancer. Cell, 171(7): 1611-1624 2017.
Haipeng Shen and Jianhua Z Huang. Sparse principal component analysis via regularized low rank matrix approximation. JMA, 99(6):01551104, 2008
Martin Sill, Sebastian Kaiser, Axel Benner, and Annette Kopp-Schneider. Robust biclustering by
sparse singular value decomposition incorporating stability selection. Bioinformatics, 27(15): 2089-2097, 2011.
Larry Stockmeyer. The set basis problem is NP-complete. IBM Thomas Division, 1975.
Watson Research
Itay Tirosh, Benjamin Izar, Sanjay M Prakadan, Mare H Wadsworth, et al. Dissecting the multicellular ecosystem of metastatic melanoma by single-cell ma-seq. Science, 352(6282):189-11 2016.
Changlin Wan, Wennan Chang, Yu Zhang, Fenil Shah, Xiaoyu Lu, Yong Zang, Anru Zhang, Sha Cao, Melissa L Fishel, Qin Ma, et al. Ltmg: novel statistical modeling of transcriptional expression states in single-cell raasseq data. Nucleic acids research, 47(18); 1-el11, 2019a.
Changlin Wan, Wennan Chang, Tong Zhao, Mengya Li, Sha Cao, and Chi Zhang. Fast and efficient boolean matrix factorization by geometric segmentation. arXiv, pp. arXiv-1909, 2019b.
Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics. 10 (3):515-534, 2009.
Svante Wold. Cross-validess volss-vali estimation of the number of components in factor and principal components models. Technometrics, 20(4):397-405, 1978.
Aaron D Wyner. Random packings and coverings of the unit n-sphere. The Bell System Technical Journal, 46(9):2111-1188, 1967.
Chun-Qin Qiu Xia, Ke Han, Yong Qi, Yang Zhang, and Dong-Jun Yu. A self-training subspace clus- tering algorithm under low-rank representation for cancer classification gene expression data. IEEE/ACM transactions on computational biology and bioinformatics, 15(4):1315-1324, 2017.
Dan Yang, Zongming Ma, and Andreas Buja. A sparse singular value decomposition method for high-dimensional data. Journal of Computational and Graphical Statistics, 23(4):923 2014.
11

---

Under review as a conference paper at ICLR 2023
Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265-28) 2006.
A
APPENDIX
A.1 SUB-ALGORITIMS OF RPSP
A.1.1 SUBMATRIX PROPAGATION
The Algorithm& 3 submatrix Propagation conducts weighted sampling to generate 2' x 2' submatri- ces based on the low rankness of 2 2 submatrices. The input of Algorithm submatrix Propagation include the input matrix X. sampled 2 x 2 submatrices, their singular values E*, and the number of to be generated 2 x 2 submatrices Lt-
Algorithm 3: submatrix Propagation
Inputs: X, K,Rr-1,F3 F,,,, It.
Outputs: R2 submatrix Propagation(X: X, Et-11 L,)):
R, 4
while R < L1 do
Prob (0,
Randomly pick two non-overlapping submatrices from Re-1, denoted as R2-1 and R
W
Σ(1 E
2
Prob<W
<W then
I Row indices of R.-1(1] and Re-1[j] Column indices of R and R-- [ append(R,, X1xJ)
end
return R,
A.1.2 LOCAL LOW RANK PREDICTION
RPSP further utilizes Algorithm Local Low Rank Prediction to identify and reconstruct the local low rank matrices. RPSP computes M x N scoring matrix S in which S7, stores the frequency of observing large value of |T] among all the sampled 2 x 2 submatrices that hits to Xiz- Hence, ST. can be viewed as approximation of the probability that X,y is contained by LLR submatrix with size of 2T x 2 larger. Here we applied the Spectral Co-Clustering method developed by Dhillon et al Dhillon (2001) and the python library provided by scikit-learn Pedregosa et al.) (2011) on ST to identify local low rank submatrices. With the indices each possible local low rank matrix identified, the local patterns
ranked by the level of their top singular values normalized by the sum of all singular values. Here the local patterns of the top K significant low rank property or with the top singular values large than certain threshold form the final output of RPSP.
Algorithm 4: Local Low Rank Prediction
Inputs: M
Outputs: I J Local Low Rank Prediction(S" (T. I I + Spectral Co-Clustering(S
return I x J
12

---

Under review as a conference paper at ICLR 2023
A.1.3 OPTIMIZE THE MAX POOLING WITH RESPECT TO NULL SPACE IN ALGORITHM 1
The max pooling with respect to null space can be further optimized by clustering the random unit vectors into groups of high cosine similarities. Specifically, the randomly sampled unit vectors were first clustered by using K-mean of their cosine distance (l-cosine similarity). Then after P()).... P(r) were identified, the null space of the linear span of {P())- .P,,,.. P(r) was estimated by the union of the clusters whose center pC satisfies max max{cos( pC, P(i)).... cos( p P(r))} < cos(()). This approach effectively reduce the number of cosine distance needed to be computed.
A.1.4 ASSESSMENT OF HYPER- HYPER-PARAMETERS OF RPSP
RPSP has four typer-parameters T, C, Le, and N₁. Le (number of randomly sampled or propagated submatrices) can be determined based on the input matrix size and computational capacity. T (number of layers for submatrix propagation) is set as 4 for efficient computation. C' (threshold of Low Score) can be computed by randomly sampling 2 x 2" submatrices of pure noise from randomly shuffled X and generating an empirical null distribution of Low RankScore. N, (number of random unit vectors) can be determined by Lemma
A.2 MATHEMATICAL DERIVATIONS AND CONSIDERATIONS
A.2.1 MATHEMATICAL CONSIDERATIONS OF THE MILRR PROBLEM
The biggest challenge with local low rank submatrix detection lies that neither the row or column indices of the submatrix is known. As given in Definition 2, the low rankness property of a submatrix evaluated through the computation of its singular values, which apparently can't be evaluated until the submatrix has been presented. However, it is computationally impossible to go through all the submatrices of an input matrix. RPSP grows a submatrix of low rank from smaller ones, which utilizes two facts. Firstly, for a low rank matrix XMXN of rank r & minn(,, N), the self consistency property suggests that any Mo X No submatrix (Mo. No. 2 r) randomly sample from X is most likely to have rank of r (Lemma in Owen al. (2009).. Secondly, for given matrix, the total number of square submatrices of dimension Mo grows exponentially with Mg. The first fact indicates that, any submatrix of low rank is collage or complete coverage of its own (smaller) submatrices, which are also of low rank. The second fact indicates that the only way for us to grow local low rank submatrix is start from the much smaller submatrices. In fact, for Mo as small as 2, it is computationally feasible for us to obtain a full collection of Mo x M, submatrices that could densely cover X M By teasing out all the Mo My submatrices of low rank, we could then gradually build them up into larger low rank submatrices. The evaluation of the low rankness for a large number of submatrices now becomes computationally expensive. RPSP, our biggest contribution is that we have developed a singular value approximation method using random project to efficiently evaluate the low rankness of any given submatrix, making it possible for us to build a submatrix from its parts.
few examples can illustrate that why a global search cannot effectively solve the MLLRR problem.
We consider the following square matrices:
(1) XM x M in which X1, ~ (0, 1) i.i.d. Here X is a matrix of standard Gaussian error. The largest singular value of X is about 2/M.
(2) YM, MM in which Y., = Y', Y (O, 1) i.i.d.. Here Y is matrix of rank=1 that have the same level of mean and standard deviation as X. Noted, the largest singular value of Y is about M. (3) Z M x in which Zıj= = a. The largest singular value of Y is M x a.
Hence for a low rank sub- matrix of size V2M x 2M or smaller, whose mean and standard deviation is not different to the background's. s. it is less likely to be identified by global SVD as the largest singular value of the sub-matrix is about the same level of the largest singular value of the background noise matrix. However, if the low rank sub-matrix has a spiked mean, its largest singular valued will be amplified by the spiked mean and the top singular vector of the whole matrix is naturally sparse. Hence, LCV problem is more likely to be solved by global search while the LLR problem of insignificant mean difference between pattern and background is less likely to be detected by a global search. So, it is necessary to think alternative approach to solve the general MI.LRR problem. Noted,
13

---

Under review as a conference paper at ICLR 2023
the idea of screening large set of small submatrices and propagate the low rank property of smaller ones to bigger submatrices only involves the computing of singular values of local patterns. Hence, we do not expect that the RPSP method may have disparate performances in solving LCv and LRR problems.
A.2.2 MATHEMATICAL FORMULATIONS OF SOTA METHODS
Co-clustering methods simultaneously clusters rows and columns of two-dimensional data matrix. The general assumption is that the targeted submatrix has a larger or small mean value comparing to the background noise. The Bregman co-clustering method generates a matrix partition I,. Ju by preserving the maximum information of data X within the partitions. The approximation error J) M(J,.) represents the difference of the preserved information and original data, here J) is the mutual information and M J) M J) L(ditt (1, [d)sstt)))) Laura et al. proposed the Plaid model to detect the submatrix by fitting each entry Xij with K layers and make sure the summation of all layers Σx=1 14 JR approximate the original value. Sparse SVD based methods identify local low rank matrix by adding LI sparse panelty to a global truncated SVD fitting. However, this type of methods still demands distinct mean difference between pattern and background and trend to detect large low rank pattern that may explain the variance of the whole matrix. Lee et al. proposed the LLORMA method by using prior knowledge to select anchors of local low rank patterns. As listed in table 1, K& is the kernel function with bandwith to smooth the projection value (-(()) near the anchor points Ω. However, this type of methods,highly depends on prior knowledge that cannot solve the general MLLRR problem.
Table 2: Existing methods of MILRR
Methods
Examples
Formulation
Tasks
Assumption
Co-clustering
Bregman;
m Je Je. Στ EiELESES d(zi),Ma)
LCV
Matrix
Plaid
partition
Matrix decomposition
SSVD;
min -VV + Aul|Ul11 + +.11VI)))
LCV
Sparse
SPCA
U.V
LLR
patterns
Anchor based methods
LLORMA
min (K x(i.)) 2 (x -X) 1.J.8
submatrix
LLR
WEMAREC
detection
A.2.3 PROOFS OF LEMMA
Lemma 1. For given dimension R, denote X R as an input matrix and P RxN matrix of N randomly generated unit vectors in RR. Y = =P denotes a random projection
of X, then - IS
lim max
VE
and lim min V E Y OR. here σi n00 18$5N"
and oR the largest and smallest singular values of X. Denote P()) arg max
R
P.3
lim N R R00 P., (.
max
R Y2 0g where Sp(P denotes the null (or complemented) space ER
arg max of the linear space spanned by Pa))- Similarly, define P(r) P., Po-
EE Y3
max NR 0oo P. E Paa.... Pa. 4))
lim
ΣR 11=1
Y2 or, for E 3, 3.... R 1.
Proof. Noted, E y2 is the norm of the projection of X onto Y.j. YJJ = XP., =
UEVTP. R U. E VT. P.jj. here UEVT is the SVD of X. Then we have DR V2
EL (E En P.y Et (EL
ER (E (2( P.j)2
as U is orthogonal, both Σ&s and P.J.P. are scalars. Hence the largest and smallest Σ Y2 is
En and ERR, which are achieved when P.,, is Vi. and VÆ. respectively. As Sp(Y(a), ..., Y(r-)) is the null space of the linear span of Ya)).., Y (1- the largest projection of X onto this space is or when P.j is VT
14

---

Under review as a conference paper at ICLR 2023
A.3 EXPERIMENTAL DETAILS
Detailed experimental parameters, data and analysis are provided below. We conducted experiments on GPU server of Cray HPE EX architecture featured with 64 nodes, 4 A100 GPUs, 64 core and 256GB per node and a CPU server features 640 compute nodes, each equipped with 256 GB of memory and two 64-c 2.25 GHz, 225-watt AMD EPYC 7742 processors.
Table 3: The Singular Value Approximation and SVD Running Time C.
q=2,nc=5
Inner time(gpu) Inner time(cpu)
Svd time(cpu)
ns=1e4
0.00002
0.0003
0.9
ns=1e5
0.00002
0.0031
0.1166
ns=1e6
0.000036
0.0328
1.1563
ns=1e7
0.0002
0.3664
11.6114
ns=1e8
0.037
3.6
116
q=4,nc=27
Inner time(gpu) Inner time(cpu) Svd time(cpu)
ns=1e4
0.000027
0.00235
0.0325
ns=1e5
0.000028
0.02436
0.3077
q=8,nc=767
Inner time(gpu) Inner time(cpu) Svd time(cpu)
ns=1e4
0.000032
0.0959
0.0828
ns=1e5
0.000059
0.9422
0.8171
q=16,c==58880 Inner time(gpu) Inner time(cpu) Svd time(cpu)
ns=500
0.000349
NA
NA
9=16,nc=3544
Inner time(gpu) Inner time(cpu) Svd time(cpu)
ns=1000
0.00003
0.1071
0.0268
ns=10000
0.000056
1.07
0.2542
A.3.1 BENCHMARK OF ALGORITHM 1: SINGULAR VALUE APPROXIMATION
We have evaluated the computational efficiency and accuracy of versus conventional QR decomposition based computation of singular values. We tested Algorithm on the GPU server and QR decomposition--aasee SVD on both of the GPU server and CPU server. Noted, due to the nature of QR decomposition, it is slower on GPU compared to CPU. We tested the two methods 50 times on 10 2, 10 x 4, and 10s on average about 10t faster than QR decomposition- based SVD. We also tested the methods 50 times on 10", 106, 10" and 10 2 matrices and have observed the speed of Algorithm consistently 10 faster than conventional SVD.
8 matrices. The Algorithm 1 used less than 10-4 4 second, which is
A.3.2 PARAMETER SETTINGS OF RPSP
In this study, we T and have validated this setting can accurately identify LLR submatrices in different scenarios. In this study, we set N1 =40, N₂ =200, N₃ =2000, and N4 =6000 that guarantee almost surely that the max cosine distance between any 2, 4, 8, and 16 dimension vector and the random unit vectors is larger than 0.98, 0.95, 0.92 and 0.8, respectively. We set the initial L,=107, L, 10 some scores with random probability. This accumulation strategy can help our model learn from the previous iterations, and thus drastically reduce the running time and increase accuracy.
L._1 and we also accumulated the scoring matrix St by adding St-1, and forgetting
15

---

Under review as a conference paper at ICLR 2023
A.3.3
PARAMETER SETTINGS OF BASELINE METHODS
RPSP is implemented by python 3,9.8 version and the python libraries numpy (1. 11.00
et al. (0220). pandas(1.44 (1.4.) 1.4.1
pandas development team
2020). pytorch Paszke et al.
(2019
n0mmaa0.5000.. Lam al. (2015) etc.
The baseline methods includes SSVD Yang et al. 2014)) SPCA Erichson et al. (020), Plaid Lazzeroni
Owen (002), CC [aneejee et al. (2007). LLORMA Lee et al. (2016). The first four methods were implemented in R environment. For SSVD, we used R package ssvd (version 1.0) and default parameters. For SPCA, we used R package sparsepea (version 0.1.2) and default parameters. For two bicluster methods Plaid and CC, we used R package biclust (version 2.0.1) Specifically for Plaid, we set 'backrround' parameter as True, 'fit.model' parameter as y ~ m + a + as tutorial. And for CC method, the parameter å and
1.0 and 1.5 as instructed by the tutorial.
For LLORMA, we used the Global LLORMA from author's GitHub with library Tensorflow GGU 1.4.0. For synthetic data experiments, all experiments were conducted by setting PRE RANK=1 along with other default parameters. In real-world data experiments, we set PRE_RANK RANK 10 along with other parameters in default. We used default learning rate parameter for all cases except for when testing the time consumption on input matrices of sizes 10000 x 10000 and 5000 x 5000, where the learning rate is set be PRE LARNING RATE 2c-5.
A.3.4 EVALUATION METRIC OF SYNTHETIC DATA BASED EXPERIMENTS
For the simulated data. The Accuracy of detecting the pattern and the back ground noise is used in our experiments to evaluate the performance of RPSP and the benchmarks. For one simulated input matrix X. N we labeled the true pattern "1" and the back ground noise as "O". We keep tracking the index of the true pattern, thus we could generate a binary matrix as the ground-truth X GTMXN If we define the output from the methods above to be output and change the non-zero get the criterion of True Positive(TP). True Negative(TN), False Positive(FP), False Negative(FP) and the Accuracy by the following function:
elements in X N to "1". We could get the output binary matrix GTMXN output- Then
TP, FP, FN, TN +- Usion Matria GTMXN)
outpat:
(1)
TP TN Accuracy T FP+
(2)
Note that in some simulation settings, the method SPCA failed, so we gave its Accuracy of In fact, all "0" Accuracy in the figures are because the methods could failed to give output. For method CC, it sometimes detects the whole matrix as one pattern matrix, meaning that CC could not identify any of the true pattern. Under evaluation metrics, CC will result in 1P=... so we gave the Accuracy of 0.5.
A.3.5 REAL.- DATA PROCESSING
MovieLens data: We have gotten the permission from GroupLens to use the MovieLens Harper & Konstan 2015) in our experiments and the datasets don't include sensitive in- formation. Movielens 25M data contains the ratings of 62,000 movies by 162,000 users. The MovieLens data is commonly used benchmark data for pattern detection. To ensure the rigor of evaluation, we selected the top 600 active users(rows) and the 600 most rated movies(columns) to build testing dataset with density rate of 20.0%. This is relatively sparse dataset. Indeed, on high sparsity dataset, all baseline methods tend to identify LCV submatrices, but still RPSP is more favorable than others terms of the low rankness and coverage rate of the detected patterns.
Single Cell RNA--equenciieeeeeeeeeeeeeeeee data: Single cell ZNA-sequencing (scRNA-seq) is high throughput technique that measures the gene expression profile of individual cells Tirosh al. (2016); Puram et al. (017). The researchers are allowed to use the dataset in their study and the datasets don
16

---

Under review as a conference paper at ICLR 2023
include sensitive information. The real application performed on two biomedical datasets, which melanoma and head and neck cancer scRNA-seq data. We collected these two datasets from Gene Expression Omnibus (GEO) database, with accession ID GSE72056 and GSE103322. The cell type label and sample information provided in the original work were directly utilized. The GSE72056 data is collected human melanoma tissues. The original paper provided cell classification and annotations including B cells, cancer-associated fibroblast (CAF) cells, endothelial cells, macrophage cells, malignant cells, NK cells, T cells, and unknown cells. The GSE103322 data is collected on head and neck cancer tissues. The original paper provided cell classification and annotations including cells, dendritic cells, endothelial cells, fibroblast cells, macrophage cells, malignant cells, mast cells, myoeyte cells, and T cells. We utilized standard normalization protocol (FPKM) for both datasets, and selected the 4000 genes (rows) and 2000 cells (columns) with the highest expression values, bringing the density rates to 70. 14% (GSE77056) and 75.71% (GSE103322), Notably, as indicated by the original work, malignant cells have high intertumoral heterogencity. Theses two datasets provide great opportunity analysis the biological mechanism by identifying the local low rank pattern within data. And the total citation of two work is above 2000.
Both data sets have been utilized in more than 100 studies, in which GSE72056 contains 23684 genes and 4486 cell, and GSE103322 103322 contains 22494 genes and 5902 cell. We utilize the standardized TPM measure of gene expression level as the input. Firstly, we first conducted a standardized normalization of the data by taking log+1: X + log2( (X + 1). We further selected the 4000 genes (rows) of top averaged expression level and the 2000 cells (columns) of the top total expression level to build our input testing data X x0000x2000, The Low Rankness, Coverage Size(Size), Coverage Rate, Running Time were used as metries in our experiments evaluate the performance of RPSP and benchmark with other methods. For each submatrices calculated by the methods above, we compute its COR rate, Size(how many elements in it) and the coverage of rate of the submatrix to the input real data.
The rows represent the genes and the columns represent the cell. Each element in the matrix means the gene expression. The scRNA-seq data is sparse, the zero value in the matrix means the gene is not expressed in the cell. Thus, we just select 4000 rows and 2000 columns by their top mean value in our experiments. Specifically, the scRNA-sco data is the unstructured data, it isn' 'n't like the image data, the order of row or column doesn't 't have special mean. The experiments on scRNA-seq data, our goal is to get the local low rank submatrix from these data. The results (Fig S1) show that RPSP performances great to get the submatrices of LLR structure. The figures of Coverage Rate and Size show that RPSP can get the most obvious LLR structure submatrix and coverage enough submatrix size(product of number of row and column). The Running Time shows that RPSP has good time performance. RPSP consistently identified the local rank-1 pattern under this experimental setting.
Spatial transcriptomics data: 10x Genomics spatial transcriptomics (ST) is a recent com- mercialized technique to measure spatial coordinates associated gene expression signal from biological tissue sample, and it has a huge utilization in biomedical studies. The researchers are allowed to use the dataset in their study and the datasets don't include personal information. We collected the spatial transcriptomics data human breast cancer tissue (v1.1 section 1) from https://www. www.g/ooieecoo///eeuueeeee/////e wwtpe//sso.eesseeee//aaaastttttt consisting 13161 genes and 3798 spatial spots. The data was processed and visualized by using Seurat 4.0 R packageHao et al. (202T). Counts data were directly utilized as the input of RPSP and other baseline methods. The row represents the genes and the column represents the cell. our goal is to get the local low rank sub- matrix form this data. The result(Fig Sle) shows one case of local low rank submatrix found by RPSP.
A.3.6 EVALUATION METRICS OF REAL-WORLD DATA
Four evaluation metrics were utilized to evaluate the performance of each method, namely (I) the Low Rankness, evaluated by "1 xT of an identified local low rank matrix X
EiEr, PCC(X..,, V,),, where σ is the largest singular value and ||Xr,xJ Il- is the nuclear norm of XIex2,, (2) the Size of local low rank matrix, (3) the total Coverage Rate defined as the total number of entries in the top-k identified patterns divided by the size of the input matrix, and (4) the Running Time. In addition, context specific meaning of the identified patterns were evaluated by prior knowledge on the www/column-wiss features.
17

---

Under review as a conference paper at ICLR 2023
A.3.7
COMPREHENSIVE SUMMARY OF REAL-WORLD DATA BASED EXPERIMENTS
MovieLens
GSE72056
GSE103322
(d)
Spatial Data
(a)
0.0
Rankmess
FC
04
1.0
02
0.0
3
(b)
960
1.24
(e)
263
Det
Size
108
(c)
Time
Time
0.70
AN0 tec
Time
0.08
6,15
Coverage Rate
400
6p0
0.00
200 4po
200
up
0,02
1000
RPSP
LLORMA
SSVD
SPCA
PLAID
CC
Fig S1. Experiment real-world data.
Application on movieLens data: MovieLens 25M data contains the ratings of 62,000 movies by 162.000 users provided by GroupLen/Harper Konstan (2015). The MovieLens data is commonly used as benchmark data for pattern detection. To ensure the rigor of evaluation, we selected the top 600 active urows and the 600 most rated moviesccolumns) to build a testing dataset with a density rate of 20.0%. This is relatively sparse dataset. Indeed, on high sparsity dataset, all baseline methods tend to identify LCV submatrices, but still RPSP is more favorable than others in terms of the low rankness, coverage rate.
We evaluated the top significant local low rank matrices identified by each method. The low rankness of the top six significant local low rank matrices identified RPSP is consistently higher (~0.8) than the ones detected by bascline methods (~0..55) (Fig Sla), while the size of the patterns detected by RPSP is lower but at similar level of the ones detected by LLORMA, SSVD and SPCA Fig S1b). Although the patterns detected by RPSP is slightly smaller, their coverage rate is higher than the results of LLORMA, SSVD and SPCA. This is because the ones detected by RPSP are distinctly non-overlapping while the top patterns identified by baseline methods are heavily overlapped (Fig SIc). On this data, Plaid did not detect any pattern while CC detected large pattern formed by 309 users and 221 movies, whose low rankness is lower than the ones detected by RPSP. The RPSP has longer running time than LLORMA, SSVD and SPCA but is faster than CC. In sum, on the Moviel data, FFLRM could detect distinct local low rank matrices of specifically high low rankness.
Application on single cell RNA-seq data: Single cell RNA-sequencing (scRNA-seq) is a high throughput technique commonly used in studying complex biological systems Tirosh et al. (2016); Puram et al. (2017). A typical scRNA-seq data is a matrix of 100,00 genes (rows) in ~5,000 individual cells (columns) with density rate in the range of 5% 50%. The LCV and LLR submatrices a scRNA-seq data directly correspond to sub-population of cells with distinct functions
Wan et al. (2019)). We applied RPSP and SOTA methods two real-world seR Ne-NA-seq data that
18

---

Under review as a conference paper at ICLR 2023
most commonly utilized in testing pattern detection methods, namely GSE72056 (melanoma) and GSE103322 (head and neck cancer) Tirosh et al. 2016); Puram et al. (2017). Due to page limit, we only presented the results GSE103322 in the main text. But here, we are presenting the results for both scRNA-Seq datasets. We utilized a standard normalization protocol (FPKM) and built the testing data by selecting the 4000 genes (rows) and 2000 cells (columns) with the highest expression values, bringing the density rates to 70.14% (GSE72056) and 75.71% (GSE103322).
On the two ScRNA-seq data, both the low rankness and the size of the top patterns identified by RPSP are consistently higher than the ones detected by baseline methods (Fig Sla-b). The patterns detected by RPSP are much less overlapped than the ones detected by LLORMA and SSVD. RPSP also achieved the highest total coverage rate comparing to all baseline methods (Fig Sic). Plaid and CC only detected one local pattern, whose low rankness much lower than the ones detected by RPSP, L.ORMA and SSVD. The RPSP had longer running time than SSVD and SPCA but is faster than LLORMA and CC on the scRNA-seq data (Fig S1c). We also examined the biological meaning of the low rank patterns detected by RPSP, LLORMA and CC, by testing the enrichment of the gene features of each pattern against known biological pathways. Noted, only in RPSP, we found three local low rank matrices significantly enrich distinct biological functions including cell metabolism, cell proliferation, and antigen presentation. In summary, RPSP outperforms all baseline methods in detecting local low rank matrices on the seRNA-seq data sets, in terms of the low rankness, size, coverage rate and biological interpretability of detected patterns.
Application on spatial transcriptomic data: 10x Genomics spatial transcriptomics (ST) is a recent commercialized technique to measure spatial coordinates associated gene expression signal from biological tissue sample, and it has been widely utilized in biomedical studies. A typical ST data matrix of ~15,000 genes (rows) in ~4,000 individual spatial spots (columns). and each spot has a 2D spatial coordinate (Fig S1d). A key challenge in ST data analysis is to infer the spatially dependent biological functional variations, which could be modeled as local low rank matrices formed by functionally associated genes over a certain spatial region, i.e. a MILRR problem.
We applied RPSP and SOTA methods on the v1.1 ST data of breast cancer provided by 10xge- nomics.com, consisting of 13161 genes and 3798 spatial spots with a density rate of 40.56%. Noted, as we have seen in the MovieLens and scRNA-seq data, RPSP is the only method that detected patterns of strong low-rankness. We showcased one of the LLR patterns specifically detected by RPSP (Fig S1e). The genes of this submatrix include two major groups, MHC class-I (immune signal given from cancers) and MHC class-II II (immune signal received by immunes) antigen presenting genes. The spatial coordinates and signal level of this submatrix suggested the region of different levels of immune response in the cancer tissue (red regions in Fig S1f are of high immune response).
REFERENCES
Arindam Banerjee, Inderjit Dhillon, Joydeep Ghosh, Srujana Merugu, and Dharmendra S Modha. A generalized maximum entropy approach to bregman co-clustering and matrix approximation. Journal of Machine Learning Research, 1919 1986, 2007.
Wennan Chang, Changlin Wan, Yong Zang, Chi Zhang, and Sha Cao. Supervised clustering of high dimensional data using regularized mixture modeling. arXiv preprint arXiv:2007.09722) 2020.
Chao Chen, Dongsheng Li, Yingying Zhao, Qin Lv, and Li Shang. Wemarec: Accurate and scalable recommendation through weighted and ensemble matrix approximation. In Proceedings of the 38th ACM SIGIR, pp. 303-312, 2015.
Yao Cheng, Liang Yin, and Yong Yu. Lorslim: low rank sparse linear methods for top-n recommen- dations. In 2014 IEEE International Conference on Data Mining, pp. 90-99. IEEE, 2014.
Inderjit S Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 269-274, 2001.
N Benjamin Erichson, Peng Zheng, Krithika Manohar, Steven L Brunton, J Nathan Kutz, and Aleksandr Y Aravkin. Sparse principal component analysis via variable projection. SIAM Journal Applied Mathematics, 802)9977-1002, 2020.
19

---

Under review as a conference paper at ICLR 2023
Yuhan Hao, Stephanie Hao, Erica Andersen- Nissen, William M. Mauck III. Shiwei Zheng, Andrew Butler, Maddie J. Lee, Aaron J. Wilk, Charlotte Darby. Michael Zagar, Paul Hoffman, Marlon Stoeckius, Efthymia Papalexi, Eleni P. Mimitou, Jaison Jain, Avi Srivastava, Tim Stuart, Lamar B. Fleming, Bertrand Yeung, Angela J. Rogers, Juliana M. McElrath, Catherine A. Blish, Raphael Gottardo, Peter Smibert, and Rahul Satjaa. Integrated analysis of multimodal single-cell data. Cell. 2021. doi: 10.1016/).cel1.22111 04.0088. BtLhhtts::// /000://///...og1110100///....// 20211. 04 048
F Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm fransactions on interactive intelligent systems (tis), 5(4), 2015.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Marchhan,, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Arry programming with NumPyy. Naturrr, (ati:mg65887828535532222225 September 2020. doi: 10. 10.10388441586-000-266999 URL
Sepp Hochreiter, Ulrich Bodenhofer, Martin Heusel, Andreas Mayr, Andreas Mitterecker, Adetayo Kasim, Tatsiana Khamiakova, Suzy Van Sanden, Dan Lin, Willem Talloen, et al. Fabia: factor analysis for bicluster acquisition. Bioinformatics,
2010.
Wenpin Hou, Zhicheng Ji, Hongkai Ji, and Stephanie C Hicks. A systematic evaluation of single-cell ma-sequencing imputation methods. bioRxáv, 2020.
Da Wei Huang, Brad T Sherman, Qina Tan, Joseph Kir, David Liu, David Bryant, Yongjian Guo, Robert Stephens, Michael W Baseler, H Clifford Lane, et al. David bioinformatics resources: expanded annotation database and novel algorithms to better extract biology from large gene lists. Nucleic acids research, 35(supp 2): W 169-W6191 175, 2007.
Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A bomebased python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, pp. 1-6, 2015.
Laura Lazzeroni and Art Owen. Plaid models for gene expression data. Statistica sinica, pp. 61-86, 2002.
Joonscok Lee, Seungyeon Kim, Guy Lebanon. Yoram Singer, and Samy Bengio. Llorma: Local low-rank matrix approximation. JMLR, 17:442-465. 2016.
Mihee Lee, Haipeng Shen, Jianhua Huang, and JS Marron. Bielustering via sparse singular value decomposition. Biometrics, 66(4):1087-1095 2010.
Art B Owen, Patrick O Perry, et al. Bi-cross-validation of the svd and the nonnegative matrix factorization. The annals of applied statistics, 3(2), 2009.
The pandas development team. mandas-dev/panne Pandas, February 2020. URL https://doi (ttg:/0.521///enooooo 3509134
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http: http:://papprrsse www.eeeeurruu...oeeeee 9015 wtw--pyoooooa-----e-----a- pdf
ve sty e- www.ohhhpprroreeeeeeooooo wwwpooormmaneeeeeeeeeeeeeeeeeeee learning library..
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Couraaeeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2836 2011.
20

---

Under review as a conference paper at ICLR 2023
Sidharth V Puram, Itay Tirosh, Anuraag S Parikh, Anoop P Patel, et al. Single-cell transcriptomic analysis of primary and metastatic tumor ecosystems in head and neck cancer. Cell, 171(7): 1611-1624, 2017.
Haipeng Shen and Jianhua Z Huang. Sparse principal component analysis via regularized low rank matrix approximation. JMA, 19(6):1155-1044, 2008.
Martin Sill, Sebastian Kaiser, Axel Benner, and Annette Kopp-Schneider. Robust biclustering by sparse singular value decomposition incorporating stability selection. Bioinformatics, 27(15): 2089-2097, 2011.
Larry Stockmeyer. The basis problem is NP-complete. IBM Thomas J. Watson Research Division, 1975.
Itay Tirosh, Benjamin Izar, Sanjay M Prakadan, Marc H Wadsworth, et al. Dissecting the multicellular ecosystem of metastatic melanoma by single-cell ma-seq. Science, (52(6282):189-199 2016.
Changlin Wan, Wennan Chang, Yu Zhang, Fenil Shah, Xiaoyu Lu, Yong Zang, Anru Zhang. Sha Cao, Melissa L Fishel, Qin Ma, et al. Ltmg: novel statistical modeling of transcriptional expression states in single-cell ma-seq data. Nucleic acids research, 47e1 11 1-e111, 2019a.
Changlin Wan, Wennan Chang, Tong Zhao, Mengya Li, Sha Cao, and Chi Zhang. Fast and efficient boolean matrix factorization by geometric segmentation. arXiv,, pp. 1eXiv-190,,2019
Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics, 10 (3):515-5344 2009.
Svante Wold. Cross-validatory estimation of the number of components in factor and principal components models. Technometrics, 20(4):397-405, 1978.
Aaron D Wyner. Random packings and coverings of the unit n-sphere. The Bell System Technical Journal, 46(9):2111-211 1967.
Chun-Qin Miu Xia, Ke Han, Yong Qi, Yang Zhang, and Dong-Jun Yu. A self- subspace clus- tering algorithm under low-rank representation for cancer classification on gene expression data. 2017.
IEEE/ACM transactions on computational biology and bioinformatics,
Dan Yang. Zongming Ma, and Andreas Buja. A sparse singular value decomposition method for high-dimensional data. Journal of Computational and Graphicul Statistics, 23(4):923-942, 2014.
Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265-282) 2006.
21


Reviews:
[{"review_id": "h42E9IGjN_", "reviewer": "Reviewer_8ATp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. \n\n-----------------------------------------\nPost-Rebuttal Update:\nI 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.", "strength_and_weaknesses": "Strengths:\n\n- The paper deals with a challenging and interesting problem i.e., matrix local low-rank representation.  \n- The authors provide a method, which is based on random projections and that helps towards deriving a more efficient method relative to other approaches.\n- The authors provide numerous simulated and real-data experiments for evaluating their approach.\n\nWeaknesses:\n - 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.\n- 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?\n- 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?\n\n\nMinor Comments\n\n- Truncated SVD shouldn't be given as Definition 1.\n- In the random projection-based algorithm, what is the sensitivity in the selection of the cut-off angle \\theta? \n\n[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.\n[2] Martinsson, Per-Gunnar, and Joel Tropp. \"Randomized numerical linear algebra: Foundations & algorithms.\" (2021).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Yy8Ro8L_9V", "reviewer": "Reviewer_gxjs", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "**Strengths**\n\n- 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.\n- There are numerical experiments that showcase the workings of the algorithm in comparison to other approaches in the literature.\n\n**Weaknesses**\n\n- 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.\n- 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.\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MsS2qilrtWH", "reviewer": "Reviewer_8ysf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strength\n\n1. RPSP is supported by rigorously derived mathematical theories, e.g. Lemma 1 and 2.\n\n2. RPSP is the first method capable of handling the general MLLRM problem. \n\n3. In the experiments, RPSP outperforms all baseline methods. \n\n4. Experimental settings and parameter settings are clear. \n\nWeaknesses\n\n1. 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”. \n\n2. P is randomly generated, which is inefficient. \n\n3. As shown in Figure 4 and Table 1, even computing parallelly, RPSP has little advantage in running time. \n\n4. Lack of parameter sensitivity analysis, such as the experiments on the sensitivity of $\\theta$. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject