Unique sparse decomposition of low rank matrices
Authors: Dian Jin
Xin Bing
Yuqian Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: matrix factorization
low-rank decomposition
nonconvex optimization
second-order geometry
sparse representation
unsupervised learning

Abstract:  The problem of finding the unique low dimensional decomposition of a given matrix has been a fundamental and recurrent problem in many areas. In this paper, we study the problem of seeking a unique decomposition of a low-rank matrix $Y\in \mathbb{R}^{p\times n}$ that admits a sparse representation. Specifically, we consider $ Y =  AX\in  \mathbb{R}^{p\times n}$ where the matrix $A\in  \mathbb{R}^{p\times r}$ has full column rank, with $r < \min\{n,p\}$, and the matrix $X\in  \mathbb{R}^{r\times n}$ is element-wise sparse. 
 We prove that this sparse decomposition of $Y$ can be uniquely identified by recovering ground-truth $A$ column by column, up to some intrinsic signed permutation. Our approach relies on solving a nonconvex optimization problem constrained over the unit sphere. Our geometric analysis for the nonconvex optimization landscape shows that any {\em strict} local solution is close to the ground truth solution, and can be recovered by a simple data-driven initialization followed with any second-order descent algorithm. At last, we corroborate these theoretical results with numerical experiments

Unique sparse decomposition of low rank matrices
Dian Jin
Xin Bing Cornell University xb43@cornell.
Yuqian Zhang Rutgers University yqz. bhgggrgharruuters.eede
Rutgers University aj3700scarlletmail rutgers.
Abstract
The problem of finding the unique low dimensional decomposition of a given matrix has been a fundamental and recurrent problem in many areas. this paper, we study the problem of seeking a unique decomposition of a low rank matrix Y E R that admits sparse representation. Specifically, we consider Y = AX E _ where the matrix E R has full column rank, with < min (n. p}, and the matrix X x= is element-wise sparse. Weprove that this sparse decomposition of Y can be uniquely identified by recovering ground-trute A column by column, up to some intrinsic signed permutation. Our approach relies on solving a nonconvex optimization problem constrained over the unit sphere. Our geometric analysis for the nonconvex optimization landscape shows that any strict local solution is close to the ground truth solution, and can be recovered by a simple data- driven initialization followed with any second order descent algorithm. At last, corroborate these theoretical results with numerical experiments.
1 Introduction
The problem matrix decomposition has been a popular and fundamental topic under extensive investigations across several disciplines, including signal processing, machine learning, natural language processing [10, 11, 31, 46, 32, 8]. From the decomposition, one can construct efficient representation of the original data matrix. However, for any matrix Y E _px= that can be factorized as a product of two matrices A E Igxrr and X grx", there exist infinitely many decompositions, simply because one can use any X invertible matrix Q to construct A' = AQ and X' Q x such that Y = AX = A'X', while A' * A and X' + X. Thus, various applications, additional structures and priors are be- ing exploited to find preferred representation [22, 15]. For example, principal component analysis (PCA) aims to find orthogonal representations which retain as much variations in Y as possible [17, 23], whereas independent component analysis (ICA) targets the repre- sentations of statistically independent non-Gaussian signals [26].
In this paper, we are interested in finding unique sparse low-dimensional representation of Y. To this end, we study the decomposition of a low rank matrix Y e R2*x that satisfies
Y AX,
(1.1)
where A E IRpx is an unknown deterministic matrix, with r < min(n. p}, and X E 1R an unknown sparse matrix.
Formulation (1.1) is an important model problem in many applications. As columns of Y are viewed as linear combinations of columns of A with X being the sparse coefficient, (1.1) can be used to form overlapping clusters of the n columns of Y via the support of X with columns of A being viewed r cluster centers [12, 7]. When we form p low-dimensional representation of Y via sparse combinations, this greatly enhance the in- terpretability of the resulting representations [28, 21, 4), in the same spirit as the sparse PCA, but (1.1) generalizes to the factorization of non-orthogonal matrices.
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

To motivate our approach, we first consider the simple case that A has orthonormal columns, namely, A A = I,'. Then it is easy to see that the sparse coefficient matrix X is recovered by multiplying Y on the left by A
A A AX = X.
(1.2)
The problem of finding such orthonormal matrix A boils down to successively finding unit-norm direction q that renders q" Y as sparse as possible [34, 39, 35],
min
Y
8. t.
|qll2 =
(1.3)
sparsity
However, the natural choice of sparsity penalty, either to or f,, leads to trivial and meaning-
less solutions, as there always exists q in the null space of A" such that q" Y =0 0.
To avoid the null space of A we instead choose to find the unit direction q that maximizes the ls norm of q" y as
max q
s.t. | 1.
(1.4)
The above formulation is based on the key observation that the objective value is maximized when q coincides with one column of A (see, Section 2, for details) while the objective value is zero when lies in the null space of AT. The & norm objective function and its variants have been adopted as a sparsity regularizer However, even with this new objective function, the null space of A persists as challenge for solving the optimization problem: they form flat region of saddle points.
line of recent works [30, 44, 43, 35, 42].
This paper characterizes the nonconvex optimization landscape of (1.4) and proposes guaranteed procedure that avoids the flat region and provably recovers the global solution to (1.4), which corresponds to one column of A. More specifically, we demonstrate that, despite the non-convexity, (1.4) still possesses benign geometric property in the sense that any strict local solution with large objective value is globally optimal and recovers one col- umn of A, up to its sign. See, Theorem 3.1 in Section 3.1 for the population level result and Theorem 3.4 for the finite sample result.
We further extend these results to the general case when A only has full column rank in Theorem 3.6 of Section 3.2. To recover general A with full column rank, our procedure first resorts to a preconditioning procedure of Y proposed in Section 2.3 and then solves optimization problem similar to (1.4). From our analysis of the optimization landscape, the intriguing problem boils down to developing algorithms to recover the nontrivial local solutions by avoiding regions with small objective values. We thus propose a simple initial- ization scheme in Section 4.1 and prove in Theorem 4.3 that such initialization, proceeded with any second order descent algorithm [20, 27], suffices to find the global solution, up to some statistical error. Our theoretical analysis provides the explicit convergence rate of the statistical error and characterizes its dependence on various dimensions, such as p, r and n, as well as the sparsity of X.
Numerical simulation results are provided in Section 5. Due to the space limitation, defer all the proof along with our conclusions and discussion of several future directions of our work to Appendix.
Notations Throughout this paper, we use bold lowercase letters, like a, to represent vec- tors and bold uppercase letters, like A, to represent matrices. For matrix X, X,; denotes the entry at the i-th row and j-th column of X, with X, and X., denoting the i-th row and j-th column of X, respectively. Oftentimes, we write X., = X, for simplicity. We use grad and Hess to represent the Riemannian gradient and Hessian. For any vector E Rd we use ||ll| to denote its lg norm, for 1 < 9 S co. The notation 80 stands for {u ). For matrices, we use I| and I1-loo to denote the Frobenius norm and the operator norm, respectively. For any positive integer d, we write [d] = (1, d). The unit sphere in d-dimensional real space Ie' is written as 5d-1, For two sequences an and bn, we write a, S bn if there exists some constant C' 0 such that a, Cb, for all n. Both uppercase C and lowercase are reserved to represent numerical constants, whose values may vary line by line.
Jr is the identity matrix of size
2

---

1.1 Related work
Finding the unique factorization of a matrix is an ill-posed problem in general due to in- finitely many solutions. There exist several strands of studies from different contexts on finding the unique decomposition of Y by imposing additional structures on and X. We start by reviewing the literature which targets the sparse decomposition of Y.
Dictionary learning The problems of dictionary learning (DL) [2, 38, 19, 39] and sparse blind deconvolution or convolutional dictionary learning [13, 29] study the unique decom- position of Y AX where X is sparse and A has full row rank. In this case, the row space of lies in the row space of X, suggesting to recover the sparse rows of X via solving the following problem,
min
Y
s.t. 970. 0.
(1.5)
Under certain scaling and incoherence condiitins on A, the objetiivacchievss achieves the minimum value when q is equal to one column of A, at the same time q" Y recovers one sparse row of X. This idea has been studied and modified in strand of papers when A has full row rank [38, 39, 45, 30, 44, 35, 42, 37, 47]. In our context, the major difference rises in the matrix A, which has full column rank rather than row rank, therefore minimizing ||q" ]| as before only leads to some vector in the null space of AT, yielding the trivial zero objective value.
We would love to note that [35] uses the same objective function in (1.4) to study the prob- lem of overcomplete dictionary learning (where A has full row rank), however the opti- mization landscape when A has full column rank is significantly different from that in the overcomplete setting. The more complicated optimization landscape in our setting brings additional difficulty of the analysis and requires a proper initialization in our proposed algorithm. We refer to Appendix B for detailed technical comparison with [35].
Sparse PCA Sparse principal component analysis (SPCA) is popular method that recov- ers a unique decomposition of a low-rank matrix Y by utilizing the sparsity of its singular vectors. However, as being said, under Y = AX, SPCA is only applicable when X coin- cides with the right singular vectors of Y. Indeed, one formulation of SPCA is to solve
max Ue
tr (U Y - II| s. t. -U--,
(1.6)
which is promising only if X corresponds to the right singular vectors of Y. It is worth mentioning that among the various approaches of SPCA, the following one might be used to recover one sparse row of X, min
- u + X||x||
s.
| 1.
(1.7)
This procedure was originally proposed by [49] and [36] together with an efficient algo- rithm by alternating the minimization between u and v. However, there is no guarantee that the resulting solution recovers the ground truth.
Factor analysis Factor analysis is a popular statistical tool for constructing low-rank rep- resentations of Y by postulating Y AX + E where A E R is the so-called loading matrix with r = rank A) < min p}, X E R xa contains n realizations of a r-dimensional factor and E is some additive noise. Here only Y is observable. Factor analysis is mainly used to recover the low-dimension column space of A or the row space of X, rather than to identify and recover the unique decomposition. Recently, [7] studied the unique decompo- sition of Y when the columns of X are i.i.d. realizations of a r-dimensional latent random factor. The unique decomposition is further used for (overlapping) clustering the rows of Y via the assignment matrix A. To uniquely identify A, [7] assumes that A contains at least one X r identity matrix, coupled with other scaling conditions on A (we refer to [7] for detailed discussions of other existing conditions in the literature of factor models that ensure the unique decomposition of Y but require strong prior information on either A or X). By contrast, we rely on the sparsity of X instead of A which is more general than requiring the existence of a X r identity matrix.
NMF and topic models Such existence condition of identity matrix either or X has variant in non-negative matrix factorization (NMF) [14] and topic models [3, 8, 9], also
3

---

see the references therein, where Y, A and X have non-negative entries. Since all Y, A and X from model (1.1) are allowed have arbitrary signs in our context, the approaches designed for NMF and topic models are inapplicable.
2 Formulation and Assumptions
The decomposition of Y AX is not unique without further assumptions. To ensure the uniqueness of such decomposition, we rely on two assumptions on the matrices A and X, stated in the following Section 2.1.
Our goal is to uniquely recover from Y, up to a some signed permutation. More precisely, we aim to recover columns of AP for some signed permutation matrix P E R- To facilitate the understanding and motivate our approach, in Section 2.2 we first state our procedure for the unique recovery of A when A has orthonormal columns. Its theoretical analysis is presented in Section 3. Later in Section 2.3, we discuss how to extend our results to the case when A is more general full column rank matrix under Assumption 2.2.
For now, we only focus on the recovery of one column of A as the remaining columns can be recovered via the same procedure after projecting Y onto the complement space spanned by the recovered columns of A (see Section D for detailed discussion).
2.1 Assumptions
We first resort to the matrix X R="= being element-wise sparse. The sparsity of X is modeled via the BernouliiGGaussian distribution, stated in the following assumption.
Assumption 2.1 Assume Xij Bi Zi for [r] and j E [n], where
Bi
i.i.d. Ber(O), Zij i.id.. (0
(2.1)
The Bernoulli-Gauste distribution is popular for modeling sparse random matrices [38, 1, 39]. The overall sparsity level of X is controlled by 0, the parameter of the Bernoulli distribution. We remark that the Gaussianity is assumed only to simplify the proof and to obtain more transparent deviation inequalities between quantities related with X and their population counterparts. Both our approach and analysis can be generalized to cases where Zi are centered i.idd sub-Gaussian random variables.
We also need another condition on the matrix A. To see this, note that even when A were known, recovering X from Y AX requires A to have full column rank. We state this in the following assumption.
Assumption 2.2 Assume the matrix A E TRxx has rank A) with || 11 1.
The unit operator norm of assumed without loss of generality as one can always re-scale a², the variance of X, by llop.
2.2 Recovery of the orthonormal columns of A
In this section, we consider the recovery of one column of A when A is semi-orthogonal matrix satisfying the following assumption.
Assumption 2.3 Assume A I,..
Our approach recovers columns of A one at a time by adopting the ls maximization to penalize the sparsity of rows of matrix X. Its rationale is based on the following lemma, assuming the orthogonality among columns of A.
Lemma 2.4 Under Assumption 2.3, solving the following problem
max ||ATall s.t. ||ql1,
(2.2)
recovers one column of A, up to ils sign.
Intuitively, under Assumption 2.3, we have ||AT 1 for any unit vector q. Therefore, criterion (2.2) seeks a vector ATq within the unit ball to maximize its l norm. When corresponds to one column of A, that is, q = a; for any i E [r], we have the largest objec- tive || a. a, 1. This l norm maximization approach has been used in several related literature, for instance, sparse blind deconvolution [44, 30], complete and over-complete dictionary learning [43, 42, 35], independent component analysis [25, 24] and tensor de- composition [18].

---

The appealing property of maximizing the 4 norm is its benign geometry landscape under the unit sphere constraint. Indeed, despite of the non-convexity of (2.2), our result in The- orem 3.1 implies that any strict location solution to (2.2) is globally optimal. This enables us to use any second order gradient ascent method to solve (2.2).
Motivated by Lemma 2.4, since we only have access to Y E Rex=, we propose to solve the following problem to recover one column of A, min F(g)= =
Y d/l:
S. | = 1.
(2.3)
120
The scalar (120o"n) is a normalization constant. The following lemma justifies the usage of (2.3) and also highlights the role of the sparsity of X.
Lemma 2.5 Under model (1.1) and Assumption 2.1, we have
[F( - (1- 0) | q 9 + 0 |
(2.4)
where the expectation is taken over the randonmess of X.
Remark 2.6 (Role of the sparsity parameter 9) Lemma 2.5 implies that, for large n, solving (2.3) approximately finds the solution
min 9
(q) [1- (1-
A q +
[|
s.t. 119112 =1
(2.5)
The objective function is a convex combination of A| on the magnitude of 0. In view of Lemma 2.4, it is easy to see that solving (2.5) recovers one column < 1. Howeeer, the magnitude of 0 controls the benignness of the geometry landscape of (2.5). When A is small, or X is sufficiently sparse, we essentially solve (2.2) which has the most benign landscape. On the other hand, when @ - 1, the landscape of (2.5) is mostly determined by the eigenvalue problem? which maximizes || qll2 subject to || 1. We will demonstrate that when X is sufficiently sparse, second order descent algorithm with a simple initialization finds the globally optimal solution to (2.3) in Section 3.
[||AAqlll qlli and ||AT with coefficients depending
of A, up to the sign, as long
2.3 Recovery of the non-orthogonal columns of A
In this section, we discuss how to extend our procedure to recover from Y = AX when A is a general full column rank matrix satisfying Assumption 2.2. The main idea is to first resort to a preconditioning procedure of Y such that the preconditioned Y has the decom- position AX, up to some small perturbation, where À satisfies Assumption 2.3 and X sat- isfies Assumption 2.1 with o² 1. Then we apply our procedure in Section 2.2 to recover A. The recovered Á is further used to recover the original A.
To precondition Y, we propose to left multiply Y by the following matrix
D (YY'") + $1
E RPx
(2.6)
where M denotes the Moore-Penrose inverse of any matrix M. The resulting precondi- tioned Y satisfies
Y = DY AX+E
(2.7)
with À satisfying Assumption 2.3, X = X X S5/V/no 2 and E being perturbation matrix with small entries. We refer to Proposition 3.5 below for its precise statements.
Analogous to (2.3), we propose to recover one column of À by solving the following prob- lem
On
min 144==1
Fg(g)
Y qli
(2.8)
12
Theoretical guarantees of this procedure are provided in Section 3.2. After recovering one column of A, the remaining columns of À can be successively recovered via the procedure in Section D. In the end, A can be recovered by first inverting the preconditioning matrix D as D A and then re-scaling its largest singular value to 1.
When A is orthonormal, this eigenvalue problem processes the worst landscape as there are in- finitely many solutions obtaining the same eigenvalue.

---

3 Theoretical Guarantees
We provide theoretical guarantees for our procedure (2.3) in Section 3.1 when has or- thonormal columns. The theoretical guarantees of (2.8) for recovering general full column rank A are stated in Section 3.2.
3.1 Theoretical guarantees for semi-orthonormal
In this section, we provide guarantees for our procedure by characterizing the solution to (2.3) when A satisfies Assumption 2.3.
As the objective function F(q) in (2.3) concentrates around [()) in (2.5), it is informative to first analyze the solution (2.5). Although (2.5) nonconvex problem and has mul-
tiple local solutions, Theorem 3.1 below guarantees that any strict local solution to (2.5) is
globally optimal, in the sense that, it recovers one column of A, up its sign. We introduce the null region Rg of our objective in (2.5),
Ro {q S
||A" al 0}.
(3.1)
Theorem 3.1 (Population case) Under Assumption 2.3, assume 0 S 1/6. Any local solution to (2.5), that is not in Ry, satisfies
ā = APe
(3.2)
for some signed permutation matrix P grxr,
The detailed proof of Theorem 3.1 is deferred to Appendix F.3. We only offer an outline of our analysis below.
The proof of Theorem 3.1 relies on analysis of the optimization landscpee of (2.5) on disjoint
partitions of @ = {q E IR: || = 133, defined
R1 = R1 (C.) {qg S" 11''gl C.
(3.3)
R₂ SP \ (Ro U.).
Here C. is any fixed constant between and 1. The upper follows from the inequality that || >=>=== max; la q/s ||a]||||a||2= for any q E g0-1, The region Rg can be easily avoided by choosing the initialization such that the objective function f(g) is not equal to zero. For R₁ and Rg, we are able to show the following results. Let Hess f(q) be the Riemannian Hessian matrix of (2.5) any point q E !
(1) Optimization landscape for Ri:
Lemma 3.2 Assume < 1. Any local solution q E Rí R1(C.) to (2.5) with C. 1 recovers one column of A, that for some signed permutation matrix P
21 I-8
q = AP.1
Lemma 3.2 shows that any critical point q E Rí is either strict saddle point that there exists a direction along which the Hessian is negative, or the desired local solution that satisfies the second order optimality condition and is equal to one column of A, up to sign.
(2) Optimization landscape for Rg:
Lemma 3.3 Assume 1/3. For any point R2(C.) with C, S 1-39 ttheee exists such that
" Hess f (g) 0.
(3.4)
Lemma 3.3 implies that any critical point in Rg is saddle point that can be escaped by negative curvature. Hence there is no local solution to (2.5) in the region R2.
Vissualization of the partitions in S is available in section A.

---

Theorem 3.1 thus follows from Lemma 3.2 and Lemma 3.3, provided that
0
30.
(3.5)
0
Condition (3.5) puts restrictions on the upper bound of A. It is easy to see that (3.5) holds for any 0 1/6. As discussed in Remark 2.6, smaller 0 leads more benign optimization landscape. In light of Theorem 3.1, we now provide guarantees for the solution to the finite sample problem (2.3) in the following theorem. Define the sample analogue of the null region Ro in (3.1) as
(c,)) {q E ||
: qll S c.}
(3.6)
for any given value c, [0, 1). Theorem 3.4 (Finite sample case) Under Assumptions 2.1 and 2.3, assume 0 E (0,1/9) and
p²
r rlog
n 2 C max
log" 2 n
(3.7)
Oc.
for some sufficiently large constant C > O and any e. E 1041/4) Then with probability at least 1 , .ary local solution to (2.3) that is not in Rg(c.) satisfies
22 log n
log" n r rlog n
l AP,112 &
0r
(3.8)
On
0
n
for some signed permutation matrix P.
Here defer our discussion of technical details and full proof in section C. 3.2 Theoretical guarantees for general full column rank A
In this section, we provide theoretical guarantees for our procedure of recovering general full column rank matrix A under Assumption 2.2.
Recall from Section 2.3 that our approach first preconditions Y by using D from (2.6). The following proposition provides guarantees for the preconditioned Y, denoted as Y = DY.
The proof is deferred to Appendix F.5. Write the SVD of A = UADAVA with UA E R and VA E R being, respectively, the left and right singular vectors.
Proposition 3.5 Under Assumptions 2.1 and 2.2, assume n 2 Cr/02 for some sufficiently large
constant C > 0. With probability greater than 1 2e -e-et c'r one has
Y AX + E
(3.9)
where À = UAVI X= X/Vono2 and E ÁA
X
with
| lop
c"
(3.10)
7
Here è' and c" are positive constants.
Proposition 3.5 implies that, when n 2 Cr/0², the preconditioned Y satisfies
Y= A=I A)X AX
(3.11)
with A A = I,. This naturally leads us to apply our procedure in Section 2.2 to recover columns of via (2.8). We formally show in Theorem 3.6 below that any local solution to (2.8) approximately recover one column of A up signed permutation matrix. Similar
to (3.6), define
(c.) = {q {9EST (PESP-1
A
I c.
(3.12)
for some given value e, E [o, 1). Theorem 3.6 Under Assumption 2.1 and 2.2, assume 9 E (0, 1/9] and
C T
max { log logn
log² r
r² logn
(3.13)
0,0
c,0v0" c,0 c.v0
Then with probability at least 1 -n -err any solution a (2.8) that is not in Region R" (c.) satisfies
r log n
22 logn On
log" n 0r
r Flog n
q AP.
S
(3.14)
p2n
n
for some signed permutation matrix P.

---

The proof of Theorem 3.6 can be found in Appendix F.6. Due to the preconditioning step, the requirement of the sample size in (3.13) is slightly stronger than (3.7), whereas the estimation error of q only has an additional lo n/(2n) term comparing to (3.8).
Theorem 3.6 requires to avoid the null region (c.). in (3.12). We provide simple ini- tialization in the next section that provably avoids Rg. Furthermore, every iterate of any descent algorithm based on such initialization is provably not in Rg either.
4 Complete Algorithm and Provable Recovery
In this section, we present a complete pipeline for recovering A from Y. So far we have established that every local solution to (2.8), that not in Rg (c.), approximately recovers one column of A UA VĀ' To our end, we will discuss: (1) data-driven initialization in Section 4.1 which, together with Theorem 3.6, provably recovers one column of A; (2) de- flation procedure [38, 39, 35] in Section D that sequentially recovers all remaining columns of A. Due to the limitation of space we defer our discussion of deflation procedure in ap- pendix.
4.1 Initialization
Our goal is to provide a simple initialization such that solving (2.8) via any second order descent algorithm provably recovers one column of A. According to Theorem 3.6, such an initialization needs to guarantee the following conditions.
Condition I: The initial point (0)) does not fall into region R (c.) for some c, sat- isfying (3.13) in Theorem 3.6.
Condition II: The updated iterates (()),, for all k 2 1, stay away from (c,) as well.
We propose the following initialization
Y1n
(0)
EP-1
(4.1)
Y1
The following two lemmas guarantee that both Condition and Condition II are met for this choice. Their proofs can be found in Appendices F.7 and F.8.
Lemma 4.1 Under Assumption 2.1 and 2.2, assume 0 (0, 1/9] and
n 2 C 0 max {
log" rlog rlog" 22
3 logn
(4.2)
0
vo
holds, then, with probability al least - er the initialization (0) in (4.1) is not in region R (c+) with c, = 1/(2r).
Lemma 4.2 Let ()) for k 2 1, be any updated iterate from solving (2.3) by using any monotonic decreasing algorithm with the initial point (0)) chosen as (4.1). If
rlog n x2
max log"
8 log
(4.3)
A v0
holds, then, with probability at least - en
2e 2e-drr
d'r one has
(k)) $ (c.),,, for all 2 1,
with c, 1/(2r).
Combining Lemmas 4.1 and 4.2 together with Theorem 3.6 readily yields the following theorem.
Theorem 4.3 Under Assumptions 2.1 and 2.2, assume E (0.1/9) and (4.2) holds. Let q be any local solution to (2.8) from any monotonic decreasing second order algorithms with the initial point chosen as (4.1). With probability at least 1 cn 4e -c"r one has
r log
22 log n
r rlg
1 A.P 11 &
+
p2n
On
On
for some signed permutation matrix P.
Theorem 4.3 provides the guarantees for using any monotonic decreasing second order al- gorithms [33, 5] solve (2.8) with the initialization chosen in (4.1).
8

---

Experiments
In this section we verify the empirical performance of our proposed procedure for recov- ering under model (1.1) in different scenarios. Due to the space limit, we defer more experiments to the Appendix of this paper.
Experiment setup
To generate the data
AX, we generate the columns by using the normalized left singular vectors of R E Rexr where Ray s.dd N( 1). The sparse coefficient matrix X Rrxx are generated as X i.idd BG((). To evaluate the success of recovering one column vector of for any estimate q E SP-1, we use the following criterion,
Err (q) min (1 (g. a:) 18
(5.1)
If Err (q) S Per say the vector q recovers the ground-truth column vector of A. We choose Pe = x 10-2 in our simulation settings. To evaluate the recovery of the whole matrix A, we use the following normalized Frobenius norm between any estimate Aest and the true A:
min
I1Acst - APLE s.t. P is a signed permutation matrix.
(5.2)
VF
We first evaluate the probability of successfully recovering one column of A in two scenarios. In the first case, we vary simultaneously and r while in the second case we change n and We then evaluate the performance of our procedure, Algorithm in Section D, for recovering the full matrix A.
Recovery probability with varying 0 and
We fix pxpp= = 100 and n = x 10 while vary 0 E (0.01, 0.04...... 0.58) and r E (10,30, 30,... 70). For each pair of (0,r), we repeatedly generate 200 data sets and apply our procedure in (2.8). The averaged recovery probability of our procedure over the 200 replicates is shown in Figure 1a. The recovery probability gets larger as r decreases, in line with Theorem 3.6. We also note that the recovery increases for smaller 6. This is because smaller 0 renders nicer geometric landscape of the proposed non-convex problem,
detailed in Remark 2.6. On the other hand, the recovery probability decreases when 0 is approaching to O. As suggested by Theorem 3.4, the statistical error of estimating gets inflated as gets too small.
Recovery probability with varying n and r
Here we fix = 100 and the sparsity parameter 0 = 0.1. We vary E (10.30.... 70} and E {2000, 3000..... 12000). Figure 1b shows the averaged recovery probability of our procedure over 200 replicates in each setting. Our procedure performs increasingly better as n increases, as expected from Theorem 3.4.
Conclusion and Future Work
In this paper, we have studied the unique decomposition of a low rank matrix Y that ad- mits a sparse low-dimensional representation. Under model Y AX where has i.i.d. Bernoulli-Gaussine
entries and A has full column rank, we propose nonconvex proce- dure that provably recovers A, a quantity that can be further used to recover X. We pro- vide complete analysis for recovering one column of A, up to the sign, by showing that any second order descent algorithm provably attains the global solution with a simple and data-driven initialization, despite the nonconvex nature of the proposed procedure.
There are several directions that are certainly worth further pursuing. For instance, a com- plete analysis of the deflation procedure for recovering the full matrix A is certainly of great interest. It is also worth studying this decomposition problem in presence some additive errors, that is, Y = AX- + E. Our current procedure only tolerates E that has small entries. How to modify our procedure ure to accommodate moderate large an interesting and challenging problem that we leave to future research.

---

100
Pectviny precdd
0.0
0.4
0.2
5.05
0.25
2000
5000
4000
5500
5000
7003
8000
5000 10030 11000 12000
(a) Recovery probability versus 0: the aver- aged probability of successful recovery for dif- ferent 0 and with 100 and 1.2 10".
(b) Recovery probability versus n: the aver- aged probability of successful recovery for dif- ferent n and with 100 and 0 0.1.
References
[1] Alekh Agarwal, Animashree Anandkumar, Prateek Jain, and Praneeth Netrapalli. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Opti- mization, 2777:2277527 2016.
[2] Alekh Agarwal, Animashree Anandkumar, and Praneeth Netrapalli. Exact recovery of spansely used overcomplete dictionaries. stat, 1050:8-39, 2013.
[3] Sanjeev Arora, Rong Ge, Yonatan Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. A practical algorithm for topic modeling with provable guarantees. In Proceedings of the 30th International Conference on Machine Learning volume 28 of Proceedings of Machine Learning Reseurch, pages 280-288. PMLR, 17-19 Jun 2013.
[4] Tom Baden, Philipp Berens, Katrin Franke, Miroslav Román Rosón, Matthias Bethge, and Thomas Euler. The functional diversity of retinal ganglion cells the mouse. Nature, 529(758)) -500 2016.
[5] Roberto Battiti. First-and second-order methods for learning: between steepest descent and newton's method. Neural compulation, 4(2):141-166, 1992.
[6] Dimitri P Bertsekas and John N Isitsiklis. Parallel and distributed computation: numerical meth- ods. 2003.
[7] Xin Bing, Florentina Bunea, Yang Ning, and Marten Wegkamp. Adaptive estimation in struc- tured factor models with applications to overlapping clustering. Ann. Statist., (8455)2055-2081, 08 2020.
[8] Xin Bing, Florentina Bunea, and Marten Wegkamp. A fast algorithm with minimax optimal guarantees for topic models with an unknown number topics. Bernoulli, 2663):1765-1776, 08 2020.
[9] Xin Bing, Florentina Bunea, and Marten Wegkamp. Optimal estimation of sparse topic models. Journal of Machine Learning Research, (177))::1-45, 2020.
[10] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent dirichlet allocation. Mach, Learn. Res., 3:993-1022, 2003.
[11] Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analy- sis? Journal of the ACM (JACM), 58(3):1-37, 2011.
[12] Guanhua Chen, Patrick Sullivan, and Michael R. Kosorok. Biclustering with heterogeneous variance. Proceedings of the National Academy of Sciences, 110(30) 2013.
[13] Sky C Cheung, John Shin, Yenson Lau, Zhengyu Chen, Ju Sun, Yuqian Zhang, Marvin Müller, Ilya M Eremin, John N Wright, and Abhay N Pasupathy. Dictionary learning in fourier- transform scanning tunneling spectroscopy. Nature communications, 11(1):1-11, 2020.
10

---

[14] David Donoho and Victoria Stodden. When does non-negative matrix factorization give correct decomposition into parts? Advances in Neural Information Processing Systems, January 2004.
[15] Jicong Fan, Yugian Zhang, and Madeleine Udell. Polynomial matrix completion for missing data imputation and transductive learning. In Proceedings of the AAAI Conference Artificial Intelligence volume 34, pages 3842-3849, 2020.
[16] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressioe Sensing. Birkhäuser Basel, 2013.
[17] Karl Pearson F.R.S. Liii on lines and planes of closest systems points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559 572, 1901.
[18] Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions. Mathematical Programming, pages 1-47, 2020.
[19] Quan Geng and John Wright. On the local correctness of 1-minimization for dictionary learning. In 2014 IEÈE International Symposium on Information Theory, pages 3180-3184. JEEE, 2014.
[20] Donald Goldfarb. Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Mathematical programming, 18(1) (8(1))31440, 1980.
[21] Kelly Gravuer, Jon J. Sullivan, Peter A. Williams, and Richard Duncan. Strong human associ- ation with plant invasion success for trifolium introductions to new zealand. Proceedings of the National Academy of Sciences, (05(17):6344) ::64446349, 2008.
[22] Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factorization: Op- timality, algorithm, and applications to image processing. In International conference on machine learning, pages 2007-2015. PMLR, 2014.
[23] Harold Hotelling. Relations between two sets of variates. Biometrika, 28(3/4):321-377,1
[24] Aapo Hyvarinen. A family of fixed-point algorithms for independent component analysis. In 1997 IEÉE International Conference on Acoustics, Speech, and Signal Processing, volume 5, pages 3917-3920. IEEE, 1997.
[25] Aapo Hyvärinen and Erkki Oja. A fast fixed-point algorithm for independent component anal- ysis. Neural computation, 977):4833-142, 1997.
[26] Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural Networks, 13(4-5):411445 2000.
[27] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
[8 lan T. Jolliffe. Rotation of principal components: Some comments. Journal of Climatology, 755):507-510, 1987.
[29] Han-Wen Kuo, Yenson Lau, Yuqian Zhang, and John Wright. Geometry and symmetry in short- and-sparse deconvolution. In International Conference on Machine Learning, pages 3570-3580. PMLR, 2019.
[30] Yanjun Li and Yoram Bresler. Global geometry of multichannel sparse blind deconvolution on the sphere. CoRR, abs/ 10437 2018
[31] Zhouchen Lin. review on low-rank models data analysis. Big Data & Information Analytics, 1(2x3)):39, 2016.
[32] Cun Mu, Yuqian Zhang, John Wright, and Donald Goldfarb. Scalable robust matrix recovery: Frank-wolfe meets proximal methods. SIAM Journal on Scientific Computing, (36939999,,,,,, 2016.
[33] Yurii Nesterov and Boris T. Polyak. Cubic regularization of newton method and its global per- formance. Mathematical Programming, 108(1):177-205, 2006.
[34] Qing Qu, Ju Sun, and John Wright. Finding a sparse vector in a subspace: Linear sparsity using alternating directions. In Adounces in Neural Information Processing Systems, pages 3401-3409, 2014.
11

---

[35] Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang, and Zhihui Zhu. Analysis of the optimization landscapes for overcomplete representation learning. arXiv preprint arXie:1912.02427, 2019.
[36]
Haipeng Shen and Jianhua Z. Huang. Sparse principal component analysis via regularized low rank matrix approximation. Journal of Mullicariate Analysis, (9()):1015 1034, 2008
[37] Laixi Shi and Yuejie Chi. Manifold gradient descent solves multt-channel sparse blind deconvo- lution provably and efficiently. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 37304. IEEE, 2020.
[38] Daniel A. Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, 2012.
[39] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEÉ Transactions on Information Theory, 63(2):853-884, 2016.
[40] Paul Tseng. Convergence of block coordinate descent method for nondifferentiaabe minimiza- tion. Journal of optimization theory and applications, 109(3):475-49)) 494, 2001.
[41] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[42] Yuexiang Zhai, Hermish Mehta, Zhengyual Zhou, and Yi Ma. Understanding 14-based dictio- nary learning: Interpretation, stability, and robustness. International Conference on Learning Representations, 2020.
[43] Yuexiang Zhai, Zitong Yang, Zhenyu Liao, John Wright, and Ma. Complete dictionary learn- ing via 14-ormm maximization over the orthogonal group. J. Mach. Learn. Res., 21:165:1-165668, 2020.
[44] Yuqian Zhang, Han-Wen Kuo, and John Wright. Structured local optima in sparse blind decon- volution. IEEE Transactions on Information Theory, 66(1):419-455 2020.
[45] Yuqian Zhang, Yenson Lau, Han-Wen Kuo, Sky Cheung, Abhay Pasupathy, and John Wright. On the global geometry of sphere-constrained sparse blind deconvolution. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
[46] Yuqian Zhang, Cun Mu, Han-Wen Kuo, and John Wright. Toward guaranteed illumination models for non-convex objects. In Proceedings of the IEEE International Conference Computer Vision, pages 937-944, 2013.
[47] Yuqian Zhang, Qing Qu, and John Wright. From symmetry to geometry: Tractable nonconvex problems. arviv preprint arXix:2007.067 2020.
[48] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal stafistical society: series (statisfical methodology), 67 (2):001333 2005.
[49] Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Craphical Statistics, 15(2):265-255 2006.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Please see our abstract and intro- duction 1
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper con- forms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please check section 2 and
(b) Did you include complete proofs of all theoretical results? our appendix
[Yes] Please check
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material
URL)? [Yes]]
y (b) Did you specify all the training details (e-g,, data splits, hyperparameters, how they were chosen)? [Yes] Please check section and
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] Please check section and
(d) Did you include the total amount of compute and the type of resources used (e.g,, type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating//eleasingn new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as
URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/ /uungg/urting? [N/A]
(e) Did you discuss whether the data you are using/ ccurating contains personally
identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screen- shots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Re- view Board (TRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "k69IHY6aLjG", "reviewer": "Reviewer_zPkZ", "summary": "The paper studies the problem of decomposing a low-rank p x n matrix Y into Y = AX, where A is p x r of full column rank and X is a sparse r x n matrix.\n\nThe paper first considers the case where A has orthonormal columns. It shows that by accessing Y only, one can recover approximately all columns of A up to the signs. It constructs a minimization programme involving the Schatten-4 norm, whose solution is an approximation to some column of A. The minimization problem can be solved by second-order methods. Then one can project A away from this solution and repeat the process. The paper gives quantitative error guarantees, provided that n is sufficiently large. The paper generalizes the result of the orthonormal case to a general A by preconditioning.\n", "questions": "", "limitations": "", "rating": 9, "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": "The paper is very well written and smooth to read. I did not check the proofs for most parts except a few lemmata for the case where A has orthonormal columns. This special case is convincingly correct and I believe the generalization to the non-orthonormal case should work out.\n\nThe paper can be regarded as a follow-up paper of [34], which considers the case where A has full row rank. In this paper, A has full column rank, which creates many difficulties in the analysis, since A has nontrivial null space and the solver for the minimization problem thus has to avoid moving into the null space. Much more sophisticated analysis is therefore needed.\n\nThe weak part of the paper is the experiment section. It would be a better paper if it considers the runtime of the algorithm and comparisons with some existing methods in dictionary learning. Despite the drawback in experiments, this paper makes a solid contribution to the matrix decomposition problems and I recommend its acceptance.\n\nMinor comments:\n- Between Line 187 and 188: min (q) should be min F(q)\n- Between Line 193 and 193: min (q) should be min f(q)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NIL", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aXEXFk6-pfp", "reviewer": "Reviewer_romD", "summary": "The paper studies the problem of computing a low rank decomposition of a matrix. Specifically, let $A$ be a $p \\times r$ matrix and $B$ be a $X \\times n$ matrix. Given the matrix $Y = AX$, the authors study the problem of computing the matrices $A$, $X$. Without further assumptions, the problem is ill-defined as for any decomposition $A$, $X$ and any invertible matrix $Q$, $AQ$ and $Q^{-1}X$ is another decomposition of the matrix $Y$. \n\nThe authors make an assumption here that the matrix $X$ is sparse in particular the matrix $X$ has iid entries where each entry is independently nonzero with probability $\\theta$ and conditioned on an entry being nonzero it has gaussian distribution. Assume that $A$ has orthonormal columns. The authors argue that solving the maximization problem $\\max_{q: \\|q\\|_2 = 1}\\|q^T Y\\|_4^4$ recovers a column of the matrix $A$ upto a sign with some error additive error. Then they show that for the general case of $A$, they can use a preconditioner computed using $Y$ that would reduce the problem to the case  orthonormal matrix and additive noise matrix of small norm. \n\nThey argue that any 2nd order optimization algorithm can be used by arguing that all critical points are either close to recovering the optimal column or that they are saddle points and that there is a direction in which the hessian is negative.\n\nThey show some experiments by generating a random matrix $A$ with orthonormal columns and generating a matrix $X$ from the above described Gaussian-Bernoulli distribution. They show that as the matrix $X$ gets sparser, the probability of recovery of $A$ increases as predicted by their theorems and also that as $n$, the number of columns of the matrix $X$ increases, the probability of recovery of $A$ increases.", "questions": "", "limitations": "", "rating": 5, "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": "I think the assumption of the matrix $X$ being generated from the distribution as in the paper is very weak evident by the fact that their algorithm works just using concentration of measure. Is there any motivation for considering such a matrix $X$ and where such a setting is plausible. You mention that other references consider the same distribution but nothing more than that.\n\nEven the population case Theorem~3.1 isn't very interesting and not very insightful. For this case, the objective authors solve is $\\max_q [(1-\\theta)\\|A^Tq\\|_4^4 + \\theta\\|A^Tq\\|_2^2]$. As the assumption is that $A$ is orthonormal, if the vector $q$ isn't in the column span of $A$, then one can just perform a descent along the component of $q$ that is orthogonal to column space of $A$ to reduce the cost. For $q$ that lies in the column space, the second  term is equal to theta and so the only relevant term is the first and perturbing $q$ in the direction of $a_i$ that has the maximum $|\\langle a_i, q\\rangle|$ should increase the objective value. The proofs in the paper also seem to essentially use these facts. Under a lot of notation, the proofs obscure the simple ideas because of which they work. Clarify if my understanding is wrong and if I am missing anything here.\n\nStrengths:\n- Main part of the paper is written well and easy to follow\n- The objective used to recover the decomposition is not complicated and simple to implement\n\nTypos/Suggestions:\n- Try to motivate why the distribution of $X$ you consider is interesting and if possible extend the algorithm to more types of matrices $X$. I believe the paper could be much stronger than the current version if you solve the problem for a more general $X$.\n- The paper doesn't conform to rules of the conference. Use Times font as in the template however bad it may be :)\n- Equations 2.3 and 2.5 are missing $F$ and $f$\n- Line 185 \"accent\" -> \"ascent\"\n- Line 281 \"approximates recover\" -> \"approximately recovers\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "_CiW5WjfRBs", "reviewer": "Reviewer_wCTm", "summary": "The authors propose a new method and analysis to decompose a given matrix $Y$ as $Y=AX$ with $X$ sparse and $A$ full column rank. This is similar but different to sparse PCA and dictionary learning, and has interesting applications.\n\nThe proposed algorithm essentially recovers $A$ one column at a time (after deflation) and maximizes the $\\ell_4$ norm of the overlap of a unit-norm vector with $Y$. As the authors also state, using the $\\ell_4$ norm is not entirely new but it gives a benign optimization landscape (in particular, strict local minimizers that are close to the desired solutions).\n\nThe best results (theoretically and experimentally) are obtained when $A$ is an orthonormal matrix and $X$ is a random matrix from a Bernouilli-Gaussian distribution. The authors propose a procedure (called preconditioning) that generalizes their results (again theoretically and experimentally) to any $A$ but it is difficult to see how good the results are. In any case, the provided experiment clearly show that we do no longer have exact recovery in this case.\n\nWhile the theoretical results seem -- I did not check the proofs in the 40(!) page appendix -- nontrivial and interesting, they only apply when recovering one vector and for a random $X$ from the Bernouilli-Gaussian distribution. No results are given for general $X$. In addition, the proposed deflation strategy is a typical technique to extend to multiple vector but typically performs quite poorly when $A$ is ill-conditioned (near linear depednent columns). The authors should therefore restate their contributions in the abstract and introduction to better reflect their main contributions.", "questions": "", "limitations": "", "rating": 6, "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": "Overall impression: The main text is very well written with sufficient motivation and literature overview. The proposed method with its theoretical results is also well explained and, from a high level, look believable. However, I did not check the proofs of the claimed results in the Lemmas and Theorems since the whole appendix is 40 pages. I therefore believe this paper is more suited for a traditional journal where proofs get their deserved full attention.\n\nQuestions:\n\n1) Abstract: \"We prove that this low rank, sparse decomposition of Y can be uniquely identified, up to some intrinsic signed permutation\" and \"Our geometric analysis for its nonconvex optimization landscape shows that any strict local solution is close to the ground truth solution, and can be recovered by a simple data-driven initialization followed with any second order descent algorithm.\" Only the one vector case is proven. Please reformulate (and also at other places throughout the paper).\n\n2) Assumption 2: If $\\|A\\|_{op}=1$ is wlog, why not remove it from the assumption? Such claims are sometimes made incorrectly and here it seems it can easily be avoided.\n\n3) \"semi-orthogonal matrix\" is not really standard (despite that is appears on Wikipedia). Matrix with orthonormal columns is clearer.\n\n4) The paper (mostly) deals with the one vector case and only random $X$ from a specific distribution. The deflation idea is sensible but not elaborated much (no theoretical results and only one experiments). The random $X$ is typical but the results are clearly not applicable to general sparse $X$. I strongly recommend restating the contributions in the abstract and introduction to reflect this better.\n\n5) The theoretical guarantees seem to have a quite bad dependence on $r$ (even $r^5$). How does this compare to sparse PCA or other sparse low-rank results?\n\n6) The experimental setup is for a very nice $A$: orthonormal and incoherent columns. I would prefer a more challenging examples in the main text or appendix since the theory allows for any $A$ of full column rank. \n\n7) How close is the theory to predict the phase transitions in the experiments?\n\n8) Line 246: \"Lemma 3.2 shows that any critical point $\\bar q \\in R_1$ is either a strict saddle point or ...\" Please explain since Lemma 3.2 only deals with a local solution $\\bar q \\in R_1$.\n\n9) Thm 3.1 (and others): What is meant by \"local solution\"? A strict local minimizer?\n\n10) Remark 2.6: Why would (2.3) approach the expectation in (2.4) for large $n$ when I only solve for a single $Y$?\n\n11) Typo: footnote page 5: processes -> pocesses\n\n12) Lemma 2.5: Missing definition of $f$\n\n13) The intuition on lines 175+ for Lemma 2.4 does not give much insight why one would use the $l_4$ norm instead of the $l_2$ norm. In particular, it does not explain why I would recover a column of $A$ with the $l_4$ norm.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "M551Cp8gO2N", "reviewer": "Reviewer_cZxs", "summary": "This paper studies the unique decomposition of a low-rank matrix into sparse and full column-rank components. Explicit conditions under which such decomposition is possible (up to a signed permutation) are derived. Moreover, an initialization scheme is proposed that, together a generic second order method, guarantees the exact and unique recovery of the sparse and full column-rank components. The authors first study the setting where the full column-rank component has orthogonal columns. Then they extend their results to the general setting where this component is no longer column-orthogonal. To the best of my knowledge, the technical contributions of the paper are sound and correct.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "This paper has a strong technical component. The ideas are clear and novel, and the paper is very well-written. Below are my comments:\n\n1. While the technical contributions of the paper is significant, the paper lacks a proper motivation. In particular, the authors have not adequately explained the main applications of the considered problem. In my opinion, the proposed framework can readily be applied to various applications of sparse PCA. The authors are encouraged to provide a better motivation of their work.\n\n2. The authors claim that “The $\\ell_4$ norm objective function and its variants have been adopted as a sparsity regularizer in a line of recent works.” This is not correct, since the $\\ell_4$ norm does not impose sparsity; it rather helps recovering the full-rank component, from which the sparse component can be derived. The authors should make this clear in the revised manuscript. \n3. The authors have nicely compared their proposed technique with the sparse dictionary recovery. However, they should provide real-world and concrete case studies where the techniques based on sparse dictionary recovery fail (specifically, the full row-rank assumption), and their proposed problem must be solved instead.\n\n4. The authors must explicitly define the notion of descent algorithm in Section 4. Based on the proof of 4.2, it seems that the only requirement for the algorithm to avoid $R_0(c^*)$ is $f(x_0)\\leq f(x_1)\\leq \\dots\\leq f(x_t)$. This should be explicitly mentioned in the main body of the paper (in fact, it is one of the strengths of the proposed initialization technique).\n\n5. It is known that several first order methods, such as perturbed gradient descent also escape saddle points, but they are not guaranteed to decrease the objective function at every iteration (as required in Lemma 4.2). In light of this, do the provided guarantees only hold with second-order methods (such as trust region and cubic regularization)? The authors have not mentioned which algorithm they use in their simulations.\n\n6. My main comment is about the simulations. The authors only consider synthetically generated and relatively small scale instances to evaluate the performance of their algorithm. Moreover, in the main body of the paper, they only consider column-orthogonal A and only recover one column of A (as opposed to the full matrix). They are encouraged to add a realistic case study, showcasing the applicability of their proposed method in real life. Moreover, after carefully reading the appendix, I realized that the proposed algorithm has significantly inferior performance for a general choice of matrix A. In particular, even in the very low-rank instances (r=10), the best recovery error is around 20%, which is quite high. It is crucial that the authors explain why their simulations do match their theoretical guarantee in the general setting. I will certainly increase my overall rating if the authors successfully justify this gap.\n\n========================================\n\nAfter rebuttal: The authors have addressed my comments in the rebuttal. I strongly encourage the authors to include the simulations on general choices of matrix A in the main body of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are encouraged to address the above-mentioned comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission to NeurIPS. There is broad consensus among the reviewers that the paper presents a significant step forward on a difficult problem. The reviewers found the paper well-written and easy to read. 

Three of the four reviewers felt that the experimental aspects of the paper could have been improved. One reviewer raised concerns regarding the Bernoulli--Gaussian assumption on $X$. While the assumption is standard in the area, it nevertheless appears to be removed from practical applications. This reviewer suggested that more thorough simulations could have better covered this weakness. 

Given the interesting and nontrivial nature of the theoretical contributions, the authors are encouraged to follow-up by submitting a long version of the paper to a traditional math journal. 
Decision: Accept (Poster)