Global Identifiability of Overcomplete Dictionary Learning via L1 and Volume Minimization
Authors: Yuchen Sun
Kejun Huang
Venue: ICLR 2025 Poster (2025)
Keywords: Dictionary learning
overcomplete
sparse
identifiability
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: Overcomplete dictionary learning is globally identifiable via the proposed L1+Volume minimization if the sparse coefficients are strongly scattered in the hypercube.

Abstract: We propose a novel formulation for dictionary learning with an overcomplete dictionary, i.e., when the number of atoms is larger than the dimension of the dictionary. The proposed formulation consists of a weighted sum of $\ell_1$ norms of the rows of the sparse coefficient matrix plus the log of the matrix volume of the dictionary matrix. The main contribution of this work is to show that this novel formulation guarantees global identifiability of the overcomplete dictionary, under a mild condition that the sparse coefficient matrix satisfies a strong scattering condition in the hypercube. Furthermore, if every column of the coefficient matrix is sparse and the dictionary guarantees $\ell_1$ recovery, then the coefficient matrix is identifiable as well. This is a major breakthrough for not only dictionary learning but also general matrix factorization models as identifiability is guaranteed even when the latent dimension is higher than the ambient dimension. We also provide a probabilistic analysis and show that if the sparse coefficient matrix is generated from the widely adopted sparse-Gaussian model, then the $m\times k$ overcomplete dictionary is globally identifiable if the sample size is bigger than a constant times $(k^2/m)\log(k^2/m)$ with overwhelming probability. Finally, we propose an algorithm based on alternating minimization to solve the new proposed formulation.

Published as a conference paper at ICLR 2025
GLOBAL IDENTIFIABILITY OF OVERCOMPLETE DICTIO- NARY LEARNING VIA L1 AND VOLUME MINIMIZATION
Yuchen Sun & Kejun Huang Department of Computer and Information Science and Engineering
University of Florida Gainesville, FL. 32611, USA {yuchen. sun, xejun quanggeufl... edu
ABSTRACT
We propose novel formulation for dictionary learning with an overcomplete dictionary, i.c., when the number of atoms is larger than the dimension of the dictionary. The proposed formulation consists of weighted sum of & norms of the rows of the sparse coefficient matrix plus the log of the matrix volume of the dictionary matrix. The main contribution of this work is to show that this novel formulation guarantees global identifiability of the overcomplete dictionary, under a mild condition that the sparse coefficient matrix satisfies strong scattering condition in the hypercube. Furthermore, if every column of the coefficient matrix is sparse and the dictionary guarantees & recovery, then the coefficient matrix is identifiable well. This is major breakthrough for not only dictionary learning but also general matrix factorization models as identifiability is guaranteed even when the latent dimension is higher than the ambient dimension. We also provide a probabilistic analysis and show that if the sparse coefficient matrix is generated from the widely adopted Gaase-Gaussian model, then the m k overcomplete dictionary is globally identifiable if the sample size is bigger than a constant times (k-2 (k) m) log( (2//m) with overwhelming probability. Finally, we propose an algorithm based on alternating minimization to solve the new proposed formulation.
INTRODUCTION
Dictionary learning (DL) amounts to factor a data matrix as X AS where is sparse Tošic & Frossard 2011), which may also be known sparse coding (Olshausen & Field 1997) or sparse component analysis (Georgiev et al.) 20055) in various fields. Treating X E R or mxxi as a collection of data samples its columns, this factorization means that each sample is sparse combination of the columns of A, or in other words atoms of the dictionary. Unlike the task of compressive sensing or sparse vector recovery, in which case the dictionary matrix A is given, dictionary learning tries to find both A and S, therefore the problem is a lot more challenging. Depending on the shape of the dictionary matrix A, we may seek find a complete dictionary if A square or overcomplete dictionary if A is wide. In this paper we focus on overcomplete dictionary learning, therefore A E mmn and Rexn (or Cm and CkxR respectively) where m k.
Dictionary learning has found numerous applications in signal denoising (Elad & Aharon 2006).
audio coding (Plumbley et al. 2009), and medical imaging (Tošić et al. (010). to name just few. On the theory side, most of the existing works have focused on algorithm design. Famous algorithms include k-SVD (Aharon al. (006a)) and online dictionary learning (Mairal et al. 2009). among numerous other algorithms based generic nonconvex algorithm design with guarantee of convergence to a stationary point. More recently, there has appeared line of research that attempts to show global optimality for dictionary learning under more restrictive assumptions, such (Spielman
et al. 2012; Agarwal et al.) 2016 Arora et al. 2014 2015
Sun et al.] 20166 b Rambhatla et al.
2019
Bai et al.] 2019 /hhai et al. 202 b Shen et al. 2020) Tolooshams & Ba 2022)

---

Published as a conference paper at ICLR 2025
1.1 PRIOR WORK ON IDENTIFIABILITY OF DL
A matrix factorization model without any additional assumptions on the latent factors is known to be not unique, since we can always "insert" an invertible matrix W and W-1 as X = AS where = AW and S = WS, and one cannot distinguish whether S or S are the groundtruth sources. Furthermore, if the dictionary A is overcomplete with m < k, columns of S could include additional components that are orthogonal to the row space of A, i... S = W(S B) where AB 0, while we still have X = AS = AW- + B) = AS. If, however, a learning criterion q(A, S) is imposed so that the resulting ambiguities can only be permutations and scaling, then we say the model is identifiable, as is formalized as follows. Notice that we differentiate the identifiability of just the dictionary and the whole factorization model, which indeed not equivalent when the dictionary is overeomplete.
Definition 1 (Identifiabilitty) Consider the generative model x = A,S, where A, and S are the groundtruth latent factors. Let (A+, S+) be optimal for an identification criterion q
(A,, S.) arg min (A,
X=AS
If A and/or S satisfy some condition such that for any S.), there exist a permutation matrix II and diagonal matrix D such that A AII then say Ag is essentially identifiable, up to permutation and scaling, under that condition; if further have that S D' S., then say that the matrix factorization model is essentially identifiable, up to permutation and scaling, under that condition.
When dictionary learning was first proposed, a common learning criterion (AA, S) is simply the total number of nonzeros in S, sometimes also called the to (pseudo-)none) )nrm || If every column S is s-sparse, then via some combinatorial calculation, it has been shown that the fo-norm minimization criterion guarantees identifiability if the spark of A is at least 2s and the sample size is O((s+ 1) (t)) (Aharon et al.) (006b)) Hillar & Sommer 2013; Garfinkle & Hillar 2019). The main drawbes back is that the required sample size is usually too large to be practical. Cohen & Gillis (2019) reduced the sample complexity down to O(k² (k - s)²), but also restricted the dictionary to be complete, i.e., m k.
Another famous learning criterion for DL, inspired by the success of compressive sensing (Donoho 2006 Candès & Wakin 2008), the following formulation with (A, S) being the summation of the absolute values of S plus indicator functions that columns of A have bounded E norms:
minimize ||S|| A,S
subject
X = AS, ||Aeell 1, k.
(1)
Identifiability results based on the l norm formulation have been predominantly local, meaning the model is identifiable within a neighborhood of the groundtruth factors (A S4), while the dictionary
is restricted to be complete (and incoherent) (Gribonval & Schnass 2010 Wu & Yu 2017; Waag et al. 2020), with the sole exception of (Geng & Wright 2014) for overcomplete DL. The advantage that the sample size requirement is typically down to O(k log k) and allows the existence of dense outliers. Global identifiability is achieved by Hu & Huang (2023a) [Sun & Huang (2024) by using matrix volume criterion Al while constraining the { norms of the rows of S with the same sample complexity, although as the criterion suggests it only applies to complete dictionaries.
1.2
THIS PAPER
In this paper, we propose the following novel formulation for overcomplete dictionary learning, and show that global identifiability can be achieved under mild conditions:
minimize A.S
log det AAT + max
Σ de S111
subject to X x=At AS
(2)
2
||d B
This means the learning criterion (A, S) consists of two parts: a weighted sum of the éj norms of the rows of S and term that is proportional to the "volume" of the dictionary matrix foror an overcomplete dictionary, the volume is defined as AA (Ben-Israel 1992). Our contributions are as follows:
2

---

Published as a conference paper at ICLR 2025
1. We give deterministic characterization of global identifiability of overcomplete dictionary learning via solving 2 Our analysis shows that a sufficient condition is that 1) every column of S is at most s-sparse and A is dictionary that guarantees exact recovery of all s-sparse vectors via & minimization, and 2) the cellular hull of Se is m-sufficcently scattered in the k- k-hypereube [-1, 1j.. The resulting identifiability condition is almost minimal: the first condition is obviously necessary as otherwise S, would not be identifiable even if the overcomplete A, is correctly recovered; the second condition is slightly stronger condition than that of complete dictionary learning. It is appealing to see that no other conditions are needed to guarantee global identifiability.
2. We further provide a probabilistic characterization of when a randomly generated factor matrix satisfies the aforementioned identifiability conditions. Since we only require Ag to guarantee exact recovery of s-sparse vectors via Ej minimization, for which there exist numerous work on this topic (such when an i.idd Gaussian matrix satisfies the restricted isometry property with high probability), we will be focusing studying the sample complexity of S. We adopt the sparse- Gaussiann model, i.e., every column contains at most nonzero values that are drawn from i.i.d. standard normal and show that the resulting S satisfies the m-strongly scattered in the k-hypercube [-1, 1] with overwhelming probability if k and n is O(k?² /)) log(k//m)) Notice that it is again a sharp generalization of complete dictionary learning with sample complexity O k log(k) k)) (Hu Huang 2023a), and factor of & better than the works that focus global optimality guarantees of overcomplete DL. (Agarwal et al. 2016 Rambhatla et al.) 2019).
3. We propose an alternating minimization algorithm for the novel identification criterion of overcomplete DL. The formulation is first modified slightly by moving the exact factorization constraint as a data fidelity term in the objective function, then the overcomplete dictionary and the sparse coefficient matrices are updated alternatingly via gradient-type step. As the problem NP-hard, no known algorithm able to guarantee convergence to a global optimum. The proposed algorithm is applied to synthetically generated data to demonstrate that global identifiability can indeed be guaranteed via solving (2).
IDENTIFIABILITY ANALYSIS
In this section, we provide analysis on when solving 2 guarantees the exact recovery of the overcomplete dictionary A, and/or the sparse coefficient matrix S.. In Definition [ we mentioned that it is acceptable to recover A; up to column permutation and scaling. While column permutation does not affect the objective value of (2). column scaling does. Therefore, that is induced from solving (2). which provides important insights into the subsequent analysis of identifiability. We provide both deterministic condition and probabilistic generative model that guarantees identifiability with overwhelming probability.
first study the optimal scaling
2.1
OPTIMAL SCALING
Lemma 1. Let (A+, Sx) be an optimal solution of 2 then
lle lee V(AL (A.AT))) A. A.1 dac. c=
where duc are the optimal weights that reach the maximum of E. delle,,.1l1.
Proof. If (A,, S*) is feasible for (2). then so is (A,Y', V where is diagonal matrix with
cth diagonal entry We- Plugging (A, w, w-'Ss) into the objective of (2) and optimize with respect to y while fixing (A,, then y = should be an optimal solution. Taking the derivative with respect Ve and setting equal zero, we get
a. AA.
a, a.y. de S. O,
where a. is the cth row of A., If = is optimal, then we must have
d, lleee T.S..ll 11: = A (A,A.) A.
(4)

---

Published as a conference paper at ICLR 2025
To maximize Ne delle Sx subject to ||d]| we know from the Sauchy-Schward inequality that dac should be chosen as some scalar a times ||e]S=II1 such that
||d 11
a Ile m.
Plugging duc a into (4) and sum over I,..., k shows
Σ alle alle
Σ e=1
A (A.A.)) A. =TrA (A.A..) A. =Tr(A,AT)" A.A,
This means a 1, and therefore
holds.
2.2 IDENTIFIABILIYY ANALYSIS
Assumption 1. The columns Ag and rows Sy are scaled and counter-scaled to satisfy:
||e| v /A[(AAA))) A.
c=
Assumption 2. Rows A; and S; are both lincarly independent. Matrix A does not contain zero columns.
Assumption 3 (m-strongly scattered in the k-hypercube), Let Ct denote the k-hypereube C:- {xx R* ||>|||0 & 1}. Define Bm as the following set
Bm Diag((lq (12. 11)) Qp YVQ k Q'Q =, p Rm ||pl|a 1},
where denotes the cth row of Q. A set S E IR is m-strongly scattered in the k-hypercube if:
Bm S s Czi
2. 8B,,. mm nas = (Diag(1lg lll...., 14/ are rows of Q with Q'Q = I}, where à denotes the boundary of the set.
The definition of the set Bm involves all x m matrices with orthonormal columns Q and normalized m-vectors p. To see that Bm is indeed subset of C, notice that the rows of Q are either zero or unit norms by construction, so all elements of the vector V Vp are in [-1, 1] using Cauchy-Schwand equivalent
the sufficiently scattered condition proposed by Hu & Huang (2023a) when = k. and more restrictive when m < k. As we will see, such restriction will be useful to establish identifiability for overcomplete DL. The sufficiently scattered condition has many variations for various identifiable unsupervised learning models, such nonnegative matrix factorization (Huang et al. 2013 Fu et al. 2015 Huang et al., 2016 2018), simplicial representation learning (Fu et al. 2015; Lin
inequality. Assumption|
2015 Huang & Ful 2019), and bounded component analysis (Tatl) Erdogan] 2021 Hu & Huang 2023b] 2024). However, to the best of our knowledge, this is the first variation that is capable of guaranteeing identifiability when the latent dimension is higher than the ambient dimension. An illustration of 2-strongly seattered in the 3-hypercube is shown on the right of Figure D compared with 3-strongly scattered on the left, which is equivalent to the sufficiently scattered condition presented by Hu & Huang (2023a).
Assumption will be imposed on the cellular hull of Sg. which is defined as follows:
Definition 2 (Cellular hull). The cellular hull of finite set of vectors (Si,..., sn), stacked the columns the matrix S, is
cell( S)
se
||0||
Consider the groundtruth sparse coefficient matrix S,, if we rescale its rows to have unit l norms, denoted as S,. then ce))(S,) 5 ç C₃ due Hölder's inequality |a') bl s ||||||||||] b||oo For identifiability of overcomplete DL, we would require cell(S.) to be m-strongly scattered in the k-hypercube, as formally stated as follows:
4

---

Published as a conference paper at ICLR 2025
>-strongly scattered 3-typercube jouffictenty scattered
2-strongly scattered 3-typercibe
45.
-1
-1
05
45
An illustration of B, in R² on the right. In comparison, B3 in R² is the Euclidean ball illustrated on the left. While B3 touches the boundary of [-1, 1] at only points +, =e2, and +e3, B2 touches each face of [] at circle with radius 1, as shown in magenta on the right. In the context of dictionary learning, 3 3 complete dictionary is identifiable if cell(S;) 2 B3, shown on the left, while 2 overcomplete dictionary is identifiable if cell(S.) 2 B2, shown on the right.
Figure 1:
Theorem 1. Consider the overcomplete DL model X A.S where A, E Rm is the groundtruth mixing matrix and S. E Rkxn is the groundtruth sparse coefficient matrix. Suppose Ag and S satisfies Assumptions) and Furthermore, let Sy denote the matrix obtained from rescaling the rows of S to have unit l norms, and assume that cell(S,) .) is m-strongly scattered in the k-hypercube. Then for any solution of (2) denoted as SA), there exist a permutation matrix II and a diagonal matrix D such that A, A.... In other words, an overcomplete dictionary Ag is identifiable if the groundtruth A, and S₁ satisfies Assumptions 1 and cell(S,) satisfies Assumption
Proof sketch. Assumption asserts that rows of Ag linearly independent, there exists k m matrix Q with orthonormal columns that spans the row space of Ag. then Q p'Q = and
QQ = A (AAAh)
Ag.
Using the diagonal matrix D which is defined as
v A/ (Ar4
[Dylec
A cc
I,..,,k
(6)
and q. rows of Q defined in Assumption
3 have
[Dylec ||el VIQQ = 1l
For two wide x n matrices S; and S., there exist k x matrix W and k n matrix such that
S. S B,
where W = S s, and rows of B are in the null space of S. i.e., S.B' = 0. Denote w. and by as the cth row of W and respectively, then
|e || || bTll1 w.S00 -,00+
O|| s
If cell( S.) is m-strongly scattered in the k-hypercube, then for all ||pl| = we can find a ||@]| such that ; Qp S.O. In Appendix A we show that Se || as result,
|le 11ll |l| = ||w] = ||5, 2 D.D.D Qp = w.Qpp. V||p =
Choose Q w @ well2. have ||e.S.1l I w. Square both sides and sum c = l,..., & we get
Q W
Q w 11 1 < Σ
le..s TrA (A,A)) A, m.
(8)
cwl
5

---

Published as a conference paper at ICLR 2025
Since both (A,Ss)) and (A,, S+) feasible, X AA5 A.S, (WS, B). Multiplying both sides by s gives
A; = A.S.S =A,(WS + B)S A.W.
Then have
log det A.A, log det A (aw'(w") (W")"A? leg Ag4 + log det Q Q
(9)
where the first inequality is shown in Appendix A Regarding the second term, we have
log det Q w (W
z log det Q Qww'QQ
(10a)
m log
| @QwwTT1
(10b)
m
where (10a and (1Ob) are shown Appendix A Combining
8 and (10) shows that
log det A.A. 2 log det det A.4.
(11)
On the other hand, since S.) is optimal for (2) we have
log det A, + max ddll- c=l
Σ
de Sclle s log det A,A,
max
Σ
de lle
||dli= c=
Lemma D and Assumption T
shows that
max
de delle..slll
max |
de Selle m,
||d F=
therefore
log det A,A, s log det A.A
(12)
Combining
11 and 12 shows that A, when scaled according to Assumption 1 any of its column permutation and/or sign flips, is optimal for (2). In Appendix(A) we complete the proof that the second requirement of m-strongly scattered in the k-hypercube guarantees that every solution must satisfy A₂ A, DII, where is diagonal matrix with only + on the diagonal, hence the overcomplete dictionary is identifiable.
Our analysis so far has not explicitly mentioned the sparsity of Sg. which may seem somewhat counter-intuitive. The explanation two-fold: the next subsection, we will show that S, follows sparse generative model, then cell(S,, (S,) will be m-strongly scattered in the k-hypercube with very high probability, thus sparsity implicitly implied Assumption 3 In particular, our analysis shows that it is necessary that every column of S₁ contains Theorem Tonly shows that the dictionary A; is identifiable, but an overcomplete dictionary it does not necessarily mean that the sparse coefficient Sy is identifiable. Fortunately, with the knowledge of the dictionary. the identifiability the sparse coefficients has been studied extensively (Donoho) 2006 Candès & Wakin 2008). Here provide general result.
more than nonzeros. On the other hand,
Assumption 4. Every column of Sy contains at most nonzeros. In addition, A, is dictionary such that for every so with no more than s nonzeros, So is the unique solution to the following optimization problem
minimize ||s||ı
subject to A,D s A.D so.
so.
where D, a diagonal matrix with cth diagonal defined 66.
Corollary 1. Consider the overcomplete DL model X = A,S, where A, E RRmk is the groundtruth mixing matrix and S2 E R is the groundtruth sparse coefficient matrix. Suppose A and Sy satisfies Assumptions 7 Then for any solution of (2), denoted as (A,,S,), there exist a permutation matrix II and diagonal matrix D such that Ag A, DII and S 11 DDDS- -

---

Published as a conference paper at ICLR 2025
Proof. Theorem shows that Aş is identifiable if Assumption are satisfied. Assumption guarantees that S is uniquely determined A, is given. To see this, we fix A A, in From Lemmal] [ we know that the optimal d should be the diagonal of D; defined in Assumption Then optimizing (2) with respect to is equivalent to the following problem with a change-of- -ariibbble D
minimize
|S|
subject to X A; = A.D.'S.
If every column of Sy is at most s-sparse, then the optimal S, = Dr therefore S, = Sq. The result still holds if columns of A are permuted and/or multiplied with +1.
2.3 SAMPLE COMPLEXITY ANALYSIS
Theorem T states that overcomplete dictionary Ag is identifiable if Assumptions 1-3 are satisfied. Assumptrons T andd 2 are quite easy to satisfy, as very reasonable to assume that rows of wide matrices A and S2 are linearly independent, and given any A₃ and S; one always find the scaling to satisfy (5) The most crucial condition is Assumption 3 or the fact that cell(S;) m-strongly scattered in the k-hypercube. In this section assume that sparse coefficient matrix S is generated model, which has appeared (Wu Yu 2017] Wang al. 2020), and show that in this case Assumption ii satisfied with high probability. This different generative model than prior works that also use a volume criterion for complete DL (Hu & Huang 2023a; Sun & Huang 2024), in which
from the sparse-Gaussin
Carnoulli-Gaussiie model is considered. This is because such generative model cannot guarantee that every column of S at least s-sparse, thus Corollary [ cannot be invoked identify both A; and Sg.
Assumption 5 (Sparse-Gaussian Gaussian model). The matrix S E Rkxn is generated from sparse- Gausssann model with parameter k, denoted as SG(s), every column of S is independently and identically distributed from the following process: subset I of size is uniformly drawn from all size-s subsets of (I,..., k). let s E IR be such that s; if and sj ~ N(O, 1) if $ I, where N(O, 1) stands for standard normal distribution.
To check whether B,, S. ce)l(S), where š is obtained from scaling its rows to have unit & norms, easier to equivalently check its polar version cell(S)) s B where the polar of set is defined as S = (x x s 1, Vy E S). For cS) its polar has a relatively simple form
(S) = {ww ||
S|1 s 1].
The polar for Bm has a more complicated form
B
[ Q Diag(Ilq (12,, |1 12)
w|l2 ( V vQQ== 1)
Therefore, checking whether (S) ç B% equivalent checking whether the optimal value of the following problem equals 1:
maximize Q.u
I| w|1
subject to || s 11 1
(13)
where D Diag (lq ll....., 11
Theorem 2. Suppose S Rkxn is generated from the pparseGGaussian model SG(s), where m. and S is obtained by scaling its rows to have unit E norm. Then
k
k-
52 n
Pr sup || S1 Q'Q=I
s 4exp
log
(14)
2
m
k3
The probability goes exponentially fast
222
k²
n = 0
log m
7

---

Published as a conference paper at ICLR 2025
The proof is relegated to Appendix Comparing this result prior work complete DL (Hu & Huang 2023a). in which case the sample complexity O(k log k), we see that the bounds agree when k, which is good sign that the bound is tight. On the other hand, there is step in the proof that shows that for overcomplete DI., it is necessary that every column of at most s-sparse, where m: this is not required for complete DL.. This shows the necessity of adopting the sparse-Gaussian model rather than the Cannouli-Gauussian model, even if identifiability of S is required. In fact, even the most relaxed condition on sparse recovery would require < m/2, so assuming S ~ (G(s) with < m is very reasonable assumption in practice.
3 ALGORITHM VIA ALTERNATING MINIMIZATION
We will now design an algorithm for the novel formulation (2) for overcomplete DL, whose global correctness in recovering the ground-truth dictionary has been theoretically established above. The main idea is similar to the (inexact) alternating optimization framework that most DL algorithms adopt. First of all, since most practical applications admit approximate factorization, we move the constraint X = AS in (2) as a penalty term as follows
1 ||AS - x1| + log det AA" max Σ delle
minimize A.S
(15)
where the hyper-parameter A. balances data fidelity and the identifiability criterion. The rest of this section will focus on designing an iterative algorithm for solving (T5). We denote (A,, S,) as the updates obtained at the /th iteration. In alternating fashion, A obtained by fixing S,, and S,+1 is obtained by fixing A = Af+1.
3.1
UPDATE OF A
Fixing S,, the update of A amounts to solving log-determinant regularized least squares, which nonconvex optimization problem. We propose two types of updates:
Gradient descent. As the gradient of (1/2) log det AAT at is (A)T, simple choice of update is to move along the negative gradient direction with step size
A+t1 - -X)S + (4)))
Majorization minimization. Notice that the log determinant of a positive definite matrix is concave, therefore
log det AA < log det A,A, + Tr[(A - A,
This defines quadratic majorization function for (1/2) log det AAT. Minimizing this term plus the fitting term with respect to A amounts to solving the following linear equation:
A(AS; X)S; + (A,4))- - 0.
This is Sylvester's equation, which can be solved by taking the eigen-decompossition of S,S, and A.A.
For simplicity, resort to the gradient descent update in the rest of this paper.
3.2 UPDATE OF S
If d is fixed, then the subproblem of S is ej regularized least squares problem, which has been extensively studied. It known to have no closed-form solutions, which not preferable as one step of an iterative algorithm. Thus, we propose to update S with a proximal gradient step. Since it amounts to getting linear approximation at S,, we also set the optimal choice with S,, which is easy to obtain from Cauchy-Schwarz:
m
de
le ll.
(16)
Σ 1=
|,e
8

---

Published as a conference paper at ICLR 2025
As result, the proximal gradient update of S with step size y take the form
S1+1 - Tya (S, yAA, (ArrSS, -))),
where (-)(+) is the soft- soft-thresholding operator on a matrix with & rows, and the threshold for components on the cth row de/y.
3.3 SUMMARY AND EXPERIMENTAL DEMONSTRATION
The proposed algorithm based on alternating minimization is summarized in
Algorithm Solving (14) via alternating minimization
initialize Ag and So
2: for = 0, 1, ....... until convergence do
3: Ar+1 - A, - y (A(AS) - x)S; + (A))
4: for l,..,, do
5: de =
Σj Se1l S,111
m
6: end for
7: S1+1 - Fya (S, - Y.A 141 (Ar+1S, X))
8: end for
As (14) is nonconvex and NP-hard, no known algorithm is able to guarantee convergence a global optimum. In the following, we provide brief demonstration of the performance of the proposed algorithm. Admittedly, the proposed formulation with identifiability guarantees opens up new direction for research algorithm design for dictionary learning, which is a challenging task in itself as it involves several terms that are nontrivial handle.
We synthetically generate random problems with =, m = 10, k = 20, and n = 200. A groundtruth sparse coefficient matrix S e Rkxn is generated from the sparse-Gaussian model SG(s), while the groundtruth dictionary A₂ mR is simply generated from a standard normal distribution. The data matrix is then generated X A.S.. Algorithm runs X with A 1000 (since want the data fidelity term to be almost zero) and y 10-5 At the end, both columns of A and A, are scaled to unit l norm, and the Hungarian algorithm (Kuhn) 1955) is used to find the best column matching. The resulting estimation error || - A remains approximately 10-8 over multiple runs. Considering the Ag is 10 x 20 with unit column norms this is satisfactory initial result.
4 CONCLUSION
In this paper, we provide perhaps the first identifiability analysis of matrix factorization model when the latent dimension higher than the ambient dimension, namely the overcomplete dictionary learning problem. Classical works on this problem rely on combinatorial mathematics, which in turn requires the sample size to be factorial to the latent dimension. Our work is based on novel formulation that uses hybrid of weighted e norm of the sparse coefficients and the volume of the overcomplete dictionary as the identification criterion, and we show that identifiability of the overcomplete dictionary of size k can be guaranteed the cellular hull of the sparse coefficient matrix is m-strongly scattered in the k-hypercuhe. If the sparse coefficient matrix generated from the sparse- Gaussian model, then such identifiability condition can be satisfied with very high probability if the sample size is ((k2)) /)) log(k? m)). which is a huge improvement compared to prior work with factorial complexity. We also propose an algorithm for the novel overcomplete dictionary learning formulation. The proposed novel formulation for overcomplete DL with a global identifiability guarantee leaves much room for faster and more efficient algorithm design.
geometric condition satisfied, namely
sparse-Gaussian
ACKNOWLEDGMENTS
This work is supported in part by NSF ECCS-2237640 and NIH R01LM01402

---

Published as a conference paper at ICLR 2025
REFERENCES
Alckh Agarwal, Animashree Anandkumar, Prateek Jain, and Praneeth Netrapalli. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optimization, 26 (4):2775-2799, 2016.
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing over- complete dictionaries for sparse representation. IEEE Transactions on signal processing, 54(11): 431 13222, 2006a.
Michal Aharon, Michael Elad, and Alfred M Bruckstein. On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them. Linear algebra and its applications, 416(1): 48-67, 2006b.
Sanjeev Arora, Rong Ge, and Ankur Moitra. New algorithms for learning incoherent and overcomplete dictionaries. In Conference Learning Theory, pp. 779-806. PMLR, 2014.
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. In Conference on Learning Theory, pp. 113-149. PMLR, 2015.
Yu Bai, Qijia Jiang, and Ju Sun. Subgradient descent learns orthogonal dictionaries. In International Conference on Learning Representations, 2019.
Adi Ben-Israel. A volume associated with mxn matrices. Linear algebra and its applications, 167: 87-111, 1992.
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962.
Emmanuel Candès and Michael Wakin, introduction to compressive sampling. IEEE signal processing magazine, 25(2):21-30, 2008.
Jeremy E Cohen and Nicolas Gillis. Identifiability of complete dictionary learning. SIAM Journal Mathematics of Data Science, 13)):11-5336 2019.
David L Donoho. Compressed sensing, IEEE Transactions on information theory, 5284):1289-1306, 2006.
Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions Image processing, 15(12):3736-3745, 2006.
Xiao Fu, Wing-Kin Ma, Kejun Huang, and Nicholas D Sidiropoulos. Blind separation quasi- stationary sources: Exploiting convex geometry in covariance domain. IEEE Trunsactions Signal Processing, 63(9):2306-22) 2320, 2015.
Charles Garfinkle and Christopher J Hillar. On the uniqueness and stability of dictionaries for sparse representation of noisy signals. JEEE Transactions on Signal Processing. 67(2)):5884 5892, 2019.
Quan Geng and John Wright. On the local correctness of 1l-minimization for dictionary learning. In 2014 IEEE International Symposium Information Theory, pp. 3180-3184. IEEE, 2014.
Pando Georgiev, Fabian Theis, and Andrzej Cichocki. Sparse component analysis and blind source scparation of underdetermined mixtures. IEEE transactions on neural networks, 16(4):992-996, 2005.
Rémi Gribonval and Karin Schnass. Dictionary identification -spooo fj-minimization. IEEE Transactions Information Theory, 56(7):35233339) 2010.
via
Christopher J Hillar and Friedrich T Sommer. When can dictionary learning uniquely recover sparse data from subsamples? IEFE Transactions on Information Theory, (::29006299)9 2015.
Jingzhou Hu and Kejun Huang. Global identifiability of e based dictionary learning via matrix volume optimization. Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023a.
10

---

Published as a conference paper at ICLR 2025
Jingzhou Hu and Kejun Huang. Identifiable bounded component analysis via minimum volume enclosing parallelotope. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023b.
Jingzhou Hu and Kejun Huang. Complex bounded component analysis: Identifiability and algorithm. In IEEE International Conference Acouslics, Speech and Signal Processing (ICASSP). IEEE, 2024.
Kejun Huang and Xiao Fu. Detecting overlapping and correlated communities without pure nodes: Identifiability and algorithm. In International Conference Machine Learning, pp. 2859-2868,
2019.
Kejun Huang, Nicholas D Sidiropoulos, and Ananthram Swami. Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Transactions on Signal Processing, 62(1):211-22) 1-224, 2013.
Kejun Huang, Xiao Fu, and Nikolaos D Sidiropoulos. Anchor-free correlated topic modeling: Identifiability and algorithm. Advances in Neural Information Processing Systems, 29, 2016.
Kejun Huang, Xiao Fu, and Nicholas D. Sidiropoulos. Learning hidden Markov models from pairwise co-occurrences with application to topic modeling. In International Conference on Machine Learning (ICML), pp. 2073-2082, 2018.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Chia-Hsiang Lin, Wing-Kin Ma. Wei-Chiang Li, Chong- Chong-Yung Chi, and ArulMurugan Ambikapathi. Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure-pixxe pixel case. IEEE Transactions on Geoscience and Remote Sensing. 53(10):5530-5 5546, 2015.
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. In Proceedings of the 26th annual international conference on machine learning, pp. 689-696, 2009.
Bruno Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by vI? Vision Research, 37(23):331-3335, 1997.
Gilles Pisier. The volume of convex bodies and Banach space geomefry, volume 94. Cambridge University Press, 1999.
Mark D Plumbley, Thomas Blumensath, Laurent Daudet, Rémi Gribonval, and Mike E Davies. Sparse representations in audio and music: from coding to source separation. Proceedings of the IEEE, 98 (6):995-1005, 2009.
Sirisha Rambhatla, Xingguo Li, and Jarvis Haupt. Noodl: Provable online dictionary learning and sparse coding. In International Conference on Learning Representations, 2019.
Yifei Shen, Ye Xue, Jun Zhang, Khaled Letaief, and Vincent Lau. Complete dictionary learning via Ip-norm maximization. In Conference on Uncertainty in Artificial Intelligence, pp. 280-289. PMLR, 2020.
Daniel A. Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp.
37.1-37.18, Edinburgh, Scotland, 25-27 7 Jun 2012. PMLR.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions on Information Theory. 63(2):853-884 2016a.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885-914, 2016b.
11

---

Published as a conference paper at ICLR 2025
Yuchen Sun and Kejun Huang. Improved identifiability and sample complexity analysis of complete dictionary learning. In 2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 1-5. IEEE, 2024.
Gokcan Tatli and Alper T Erdogan. Polytopic matrix factorization: Determinant maximization based criterion and identifiability. IEEE Transactions on Signal Processing, 69:5431-5447, 2021.
Bahareh Tolooshams and Demba E. Ba. Stable and interpretable unrolled dictionary learning, Trans- actions on Machine Learning Research, 2022.
Ivana Tošić and Pascal Frossard. Dictionary learning. IEEE Signal Processing Magazine, 28(2): 27-38, 2011.
Ivana Tošić, Ivana Jovanović, Pascal Frossard, Martin Vetterli, and Neb Durić. Ultrasound tomography with learned dictionaries, In 2010 IEEE International Conference on Acoustics, Speech and Signal Processing, pp- 5502-5505. IEEE, 2010.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Yu Wang, Siqi Wu, and Bin Yu. Unique sharp local minimum in 11 mi-mimiiinaiion complete dictionary learning. Journal of Machine Learning Research, (1 2020.
Siqi Wu and Bin Yu. Local identifiability of Il-minimization dictionary learning: a sufficient and almost necessary condition. The Journal of Machine Learning Research, 18())6121-6176, 2017.
Yuexiang Zhai, Hermish Mehta, Zhengyuan Zhou, and Ma. Understanding 14-based dictionary learning: Interpretation, stability, and robustness. In International Conference on Learning Representations, 2020a.
Yuexiang Zhai, Zitong Yang. Zhenyu Liao, John Wright, and Yi Ma. Complete dictionary learning via 14-norm maximization over the orthogonal group. Journal of Machine Learning Research, 21 (165):1-68, 2020b.
12

---

Published as a conference paper at ICLR 2025
A PROOF OF THEOREM
In the proof sketch of Theorem
we showed that
2 log det AgA max Σ delle = log det A.A.
de d.lle.s.11.
max ||d]]
[dll]
so (Ap. St) at least one candidate solution for (2) In this section, we first complete the proof by showing that if the second requirement of Assumption 3 satisfied, then any optimal solution (A., S.) must satisfy that A, = A,IDD where If is a permutation matrix and D is a diagonal matrix
with on the diagonal.
In 8
we proved that ||e 2 I @@TTelll
Well2 lll by choosing |00| S such that
30 D QQ' w ///e/ll Q'weel2-
Suppose QTw,// Q # + 1 for all c = I,..., k, then according the second require- ment of Assumption 3 such that
it is in the interior cell( Sy). which means there exists a and ||0] S
50 aD, QQ' ww/ll
Therefore
||e.S. =| w. D.S0 al|("wellt 11QTwolla
This means equality of S.e. 2 || (Q"well2 is only attained when Q We = = 9. for some c I,...,k. Finally, it is proven in (10b) that
log det Q QW""QQ s m log - QQQ
and if det A44 det A,A, the above inequality must hold as an equality. In the proof of (0bb) we showed that equality holds only if all the cigenvalues of Q Q'Q are equal, meaning columns of WQ are orthonormal. Since itself is orthonormal, it is possible only WQQ DII' Q, where diagonal matrix with #1 on the diagonals and /I is permutation matrix. This shows that
A A,IID.
Q.E.D.
The remaining of this section shows some key equalities and inequalities the proof sketch that are skipped for clarity.
Proof that |le. ||w, As we argued in the proof sketch of Theorem the constraint X = AS is equivalent to AW Ag and S = WS, + B where S,B' O. Substituting them into ( eliminates the constraint X AS:
minimize log det AAT A.WBB
Σ
dell bill
subject to AW A.. S.B" 0.
[|
Taking the Clarke generalized derivative the Lagrange function with respect to b, and setting equal to zero gives
d.O. S. 00
where 0. sign(S, + be) and He is the Lagrange multiplier for the cth column of S.B This shows that 0, is a linear combination of rows of S,, which means is orthogonal to b.. As a result,
|ee.stll ||w + b..l1 w. b.O.- w.S.O. ||w,,
13

---

Published as a conference paper at ICLR 2025
Proof of inequality following properties:
The matrix wwt defines projection matrix, which is symmetric, with the
WW II, WW wwwww' = -ww' (WW")) =w"" (W")"T".
As result,
A.A, 2 det A.W A, der A.W" W w A. det (, (W")
where the last step is because A = A.W..
Proof of inequality 1Oap. Since A = A, W, rows Ag are in the row space W, and so are columns of Q. Therefore
ww Q Q.
This means WQ has linearly independent columns, therefore Q Q' is invertible and (Q (Q'""QQ--1 = (WQ)* (QT))
On the other hand, since Q Q'wWiQQ 1, this means
w' (WQ)* C,
where rows of C are orthogonal to columns of W., i.c. CWQ = O. Columns of WQ and rows of (WQ)) span the same subspace, also have C' (WQ)) = 0. As result,
det @ ( det (WQ)) + c) (WQ) +c)
det (Q") cCT)
de((WQ))(QW)) = det QWWQQ--
Taking the log on both sides shows
10a
Proof of inequality TTb).. Denote the eigenvalues of Q Q'W'VQ W as M,..., which are all nonneg- ative, then
1/m
(det Q Qww"wo) 1/m
Aj
TQww== 1|
where the inequality in the middle is the geometric-arithmete mean inequality. Taking the log on both sides and rearranging gives (10b). Notice that equality holds only if λ₁ Am i.c., columns of WQ are orthonormal.
B PROOF OF THEOREM 2
We assume that SG(ss, and the first thing we do is rescale its rows to have unit & norms and use it for the problem 13 To simplify the analysis, we can instead directly maximize D [|] subject to || S|] z I, and compare with the largest & norm of the rows of S. The complement of the intended probability can be bounded as
Pr
sup Sil
IIQ'D- w|l s
2 Pr
sup [ s
(Q'D-wwll a max || 2 a
Q'Q=1
with an arbitrary choice of a. Conversely,
Pr
sup
[QDD-'w) w|] >
Pr
sup
| U max ||S
I S1
Iw s Q'Q=1
Q'Q=I
S Pr
sup
[| DI' wil > a + Pr max || ||S, < a (17)
| S1 s1
Q Q'Q-I
14

---

Published as a conference paper at ICLR 2025
where the second inequality is obtained from the union bound. The rest of this section is dedicated to bounding the above two terms. Both of these results rely on the following version of the Bernstein inequality (Bennett I962):
Theorem 3 (Bersstein's inequality). Let Zn be independent random variables with E[ s 12 and there exists some constant e such that for all integer d > 2
B[IZ| $ 22 -d: ca-
(18)
Then
e²
Pr
Σ -
-[2])
> s exp
2(nv² + ce)
Lemma 2 (Bounding the second term in 17 Suppose S [Rkxa is generated from the sparse- Gaussian model (G(s). Then
Pr max ||I n(s//1) -)
n(s/k)e²
s 2k expexp
2+ v2e
Proof. Let s (S),..., Sn) be one row of S generated from (G(s), then each S; has probability s/ to be standard normal and probability 1 - s/k k to be zero. We will use Bernstein's 's incquality with Zi |sy]. Let g denote standard normal random variable, then Igl follows a Chi-distribution of degree I, its moments are
d+1
E[lg[ = 2d12 =24/2
(19)
r T(2)
As result, we have E[Z] (s/x) and B[Z,]] s/k Using the recurrence relation for bound the rest of the moments
Gamma function I'(++1) (t) and v2/r(1/2) 22 with d as
E[|Z|| (s/k) d!
(20)
24/2¹
Therefore the moments satisfy (18 with 1/V2, results in
Pr ||ا|||
n(s/))( e) Pr Σ (Zi - E[Zi) > n(s/k)E
n²(k2222
2exp
2(n(s/k) + n(s/k)e/VV)
n(s/k)E?
exx
2+ v2e
Finally, using the union bound
max ||5 < m(s/k)(v2/T - e)
$ Pr |1S n(s/k)(
n((sk)e2
< 2k exp
2+ V2.
We now proceed to bound the first term in (17). First, we note the following equivalence:
Pr sup w S 11 Q'Q=1
DD w|l > a = Pr
inf [Q w Q'Q=1
wTll < 1/a
(21)
We also going the following notion of 8-cover from geometry (Pisier
1999)s
15

---

Published as a conference paper at ICLR 2025
Definition 3 (6 (6-cover). A finite ô-cover of set S in R is finite set N(S, 6) of points on S such that any point on S is within e away from an element in W(S, 6), i..
||w - will < 6, Ab S. w)CN(S
min
well-known result is that the ô-cover of the unit sphere Bg {w ||w||2 1} has bounded cardinality (Vershynin 2018):
2 0 +
W 8)1 =
Notice that Bg is special case of Bm defined in Assumption 3 with k m, implying that Bx S Bm and thus B Bt We will use this result to prove (rather loose) bound for the 8-cover of 8
Lemma 3. The 8-cover of Bi satisfies
(N 0)12 - - +11
Proof. It is easy to see that Bg is self-polar, i.e., Bi = Bk, B c Bx. Since the superset Bg satisfies (N( 8)1 s (1 2/ so is the subset B
Lemma Let ((mm 8) = {wi} be a 8-cover for B in Rk Assume that we have both the lowerbound
(Stwilli 1 2 B, Vwi E N(Bm 6)
and the upperbound
||ST]|
sup ||m]|| sl
||ST0|| $ y.
Then
inf
w 2 β yövk
20
By definition of the 8-cover, for all w E B, we can find w E N(B, 8) with 1|w- will < 6. Therefore
Proof.
||STwil 2 1|STw,ll1 [[S w;)lli 2 f ||5 ||w will
2 B || w vk 2 B-VO
Lemma 5 (Bounding the first term in 17 model SG()). Then
Suppose S E Rkxn is generated from the sparse- Gaussian
s(2)) + 2xxp
n(s/k)2E2
||S" wll < n(s/k) OV -
Pr inf
WEB
2+ V2.
where 8 E (0, 1) represents any choice of 8-cover for B
Proof. Following Lemma we have
inf ||ST < B YOVE
Σ
Pr[1|STwille < < + Pr ||| > r].
(22)
we Se
W,EN(BB...))
where (B 6)1 (1+ 2/8)* according to Lemma
The bound to the first term in write
22 is almost identical to Lemma 2 Dropping the subscript of wy
|| =
= > 12
WijWi
1=1
-=1
i=1
16

---

Published as a conference paper at ICLR 2025
Without the absolute value, Z is normally distributed with zero mean and variance 0² EjEr, wj. where I; is the index set of nonzero elements in S; with [ s < m. Then o² S 1. To see this, suppose without loss of generality that 1, = {I,...,s} and let Q [I OJ". then w 2 implies that Ejer, w 2|@l|12 v 1. In other words, if w B the squared sum of more than elements of w must be Therefore for d
E| E
B[|Z 11 s 1,
while for d = we have
|||2/|] k
Again, the moments satisfy (88 with 1/v2, results in
Pr ||S <n(s/
2) = Pr
Σ i=1
(74 - B[Z+])
> n(s/k)e
$ 2xxp
2(n+ ((s/k)//s2)
n(s/k)
2xxp
(23)
2 V2e
To bound || we recall that this is the e induced norm for matrix S which is shown be the maximum of the f norms of the columns of ST. This means we can use similar arguments used in Lemma 2 (but applied to the other direction) to have
|ااا np(v2/x+
e)
Pr max ||S > n(s/k) 2)
Pr
|| nxs/k)(v2/2)) 2/
Pr
Σ (14 E[zi))
> n(s/k)e
n(s/k)
n(s/k)?2
$ 2 exp
S 2 exp
(24)
2 + v2e
2+ V2c
where we pick an arbitrary j [k] in the second line since this event implies that the maximum & norm of the rows is lowerbounded, and in the third line each Z; satisfies (20). The proof is complete by combining
(22
(3). and 24 with & = n(s/ ()) 22 E) and y = n(s/k)(())))) E).
Proof of Theorem
We first instantiate Lemma 5 with
= (>(s/) 2)
which satisfies 8 Of
2 π
n(skk)
Then have
x(2)) + 2exp
n(s/k)e2
Pr inf we
[[SW 1//(s/k))
2 V2e
Combining
21 and Lemma
with n(s/k)( 2/ e), obtain
Pr
sup
||m|||
Pr
inf |||||||
||St 1 1/a
Pr max ||S
|| S|]
2
n(s/k)2E2
s 2
k
2
exp
(25)
2 + V2e
17

---

Published as a conference paper at ICLR 2025
Further, with
((m/k)14- 1112/1
(m/k)1/4 +
where the right hand side is obviously positive, have
(2ss/K) -
Vm
8
n² -
2 k
We can further relax
25 to
&
n(s/k)
sup ||||| >
$2 k+ 2k/ Vm
+2 exp
2+ V2E
we Bi
|n(skkpe2 exp
- 4 2k/ Vm
2+ v2e
4exp (k/2) log(k²
(rokkk/m)//)) n(s/k)
where in the last inequality we simply picked small enough that
6²
2 V2E
This completes the proof.
18


Reviews:
[{"review_id": "ZNIkEZgiC3", "reviewer": "Reviewer_1DsL", "summary": "The paper introduces a new formulation for the overcomplete dictionary learning problem. The authors show global identifiability of the dictionary and sources up to permutation and scaling provided that the atoms are sufficiently sparse.", "questions": "Detailed Comments:\n\n- Maybe recall what complete and overcomplete (no orthogonality) dictionary mean\n- Formulation (2) should be better introduced. Why is \n- line 106, you say that A should be a dictionary that guarantees exact recovery of all s-sparse vectors. Do you mean that min ||x||_1 s.t y= Ax should have a unique solution for all s-sparse vectors?\n- line 107, what is the cellular hull?\n- you should clarify the notion of scattered cellular hull before introducing your results.\n- Statement of Lemma 1 is misleading. First of all, from what I understand the weights d_{*c} reach the maximum of \\sum_c d_c ||e_cS_*|| under the constraint \\|d\\|\\leq m. Secondly, if the max is attained for (3), why not just optimize the l1 norm squared?\n- Is it always possible to scale the columns of A_{\\#} and rows of S_{\\#} to satisfy (5). This is not obvious to me\n- If I understand well you want the set S to be reduced to canonical vectors p? and S could include vectors that are not in the span of Q but all vectors in span(Q) must be of the form q/||q||?\n- From your definition of B_m, the set is a subset of R^k (i.e. it is given by some linear combinations of the columns of Q). Moreover S is also a subset of R^k so how can the intersection of those subsets be a subset of R^m (i.e given by rows of Q)? Maybe you mean the columns of Q?\n- line 158-159, I would add just one sentence, to explain that for the correlation to be maximum, you need the cosine of the angle between the vectors to be maximum which implies d_c = \\alpha \\|e_c^T S_*\\| for all c\n- lines 164-165, there are alphas missing. \n- line 178 and Figure 1. If I understand well, the set B_m is an intersection of spheres of dimension m. If my understanding is correct, I think it would be worth mentioning it somewhere because it looks as if the points clouds in Fig 1 have non empty inerior (especially the 2-strongly scattered one) while my guess is there are empty. \n- lines 241-244, in your proof sketch, again if I understand well, you define your matrix Q from the left factor of the SVD of A_#. I.e. if you have A_# = U\\Sigma V^T, then you define Q as V. Then why not say it like that. I feel this is simpler and much more clear\n- On line 248, you refer to assumption 4 which does not appear anywhere (the hyperlink does not work)\n- line 251-253, shouldn’t the pseudo inverse be applied on the right of S_*, i.e. from line 252, the dimensions of W seems to be n\\times n to me. Moreover, what you need to project to have the decomposition of line 251 are the rows of S_* not the columns. \n- One lines 268-269, if I’m not wrong you mulyiply both sides by S_# and not S_*\n- On line 272, there is a transpose missing on the second A_#\n- On line 272, the last equality in Equation (8) is not completely clear to me. Isn’t ||e_c^T S_*||_1 = ||w_c^T S_#||_1 and not ||e_c^T S_#||_1 ? why is ||w_c^T S_#||_1 = ||e_c^T S_#||_1 ? Does the relation follow from (5) and the fact that A_# = A_*D\\Pi ? It would help to have even a short additional explanation here.\n- lines 303-305, I don’t understand the sentence. You say that the sparsity is implicitely implied in (5)? How come ?\n- lines 302 - 303 should be rephrased. I think what you mean is that “sparsity is required to have the strongly scattered condition used in the statement of Theorem 1” instead of “sparsity is implied in Assumption 1”\n- line 308 “does not necessarily mean that the sparse coefficients S_# is identifiable” —> “are identifiable” ?\n- lines 313 -320, Assumption 4 seems quite strong (or quite vague) on the dictionary. Is it easy to find such dictionaries? (I.e. you don’t provide any numerical illustration). It would be perhaps good to have a short comment such as the one at the beginning of section 2.3\n- lines 339-340, “the most crucial condition is assumption 3 that cell ..” —> “the most crucial condition is assumption 3, or the fact that cell(S_#) should be generated …”?\n- lines 341-342: “and show that when it satisfied assumption 3” —> do you mean “and show that it satisfies assumption 3”?\n- Section 2.3., lines 337-346, I don’t really understand why, if you can make it work in the sparse Gaussian model, you can’t make it work in the Bernoulli Gaussian model. If the probability in the Bernoulli distribution is set to s/n, can’t you get a result similar to what you have with sufficient probability? Even if you can’t be at least s-sparse, isn’t “at least s-sparse” with sufficient probability enough?\n- line 348 - 349 “if for every column of S” —> “if every column of S”\n- lines 362-363 : “is equal to” or “equals” but not “equals to” \n- line 380, I would remove the line “which is a good sign that the bound is tight ”\n- line 383 “even if identifiability of S_# is not required”, what do you mean “is not required”? Aren’t all your result focusing on the identifiability of S_# ? i would remove the paragraph starting from “On the other hand” because it makes everything unclear.\n- line 389 - 390, the sentence “Due to the novel formulation (2) for overcomplete …” does not make sense either. Do you mean “We will now design an algorithm for formulation (2) for which uniqueness (up to permutation and scaling) of the dictionary and sources was shown above”\n- line 427 “which is not preferable as one step of an iterative algorithm ” just remove.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper seems mathematically sound (be careful with the dimensions, see the detailed comments below). Its positioning with respect to the existing literature should be better documented though. Two results appear as particularly related: Hu and Huang 2023 and Agarwal et al/ Rambhatla et al. It would help to have a clear discussion on the improvement of the paper compared to those results.", "weaknesses": "Sparse coding or sparse dictionary learning are not new", "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": "", "extra_scores": {}}, {"review_id": "JkMGYye3YF", "reviewer": "Reviewer_z7Po", "summary": "This paper addresses the identification problem in over-complete dictionary learning by introducing a new formulation. The authors primarily build on the analysis from [Huang & Hu, 2023], extending the concept of \"sufficiently scattered\" to the over-complete setting. By combining this extension with scaling and independence conditions for $A$ and $S$, the authors argue that \"sufficiently scattered\" serves as a sufficient condition for the identifiability of $A$ under the proposed formulation (2). Additionally, they provide a theoretical guarantee that this \"sufficiently scattered\" condition holds with high probability under the commonly used Bernoulli-Gaussian distribution.", "questions": "Given that the \"sufficiently scattered\" condition has been previously introduced in NMF and topic modeling, and that similar identifiability conditions appear in [1,2], could the authors discuss the specific technical challenges posed by applying this condition in the dictionary learning (DL) setting compared to the NMF/topic modeling context? \n\n[1] Kejun Huang, Nicholas D Sidiropoulos, and Ananthram Swami. Non-negative matrix factorizationrevisited: Uniqueness and algorithm for symmetric decomposition. IEEE Transactions on Signal Processing, 62(1):211–224, 2013.\n\n[2] Kejun Huang, Xiao Fu, and Nikolaos D Sidiropoulos. Anchor-free correlated topic modeling: Identifiability and algorithm. Advances in Neural Information Processing Systems, 29, 2016.\n\n[3] P. Georgiev, F. Theis and A. Cichocki, \"Sparse component analysis and blind source separation of underdetermined mixtures,\" in IEEE Transactions on Neural Networks, vol. 16, no. 4, pp. 992-996, July 2005", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea is well-motivated, and the problem is relevant to the community. While previous work typically relies on column incoherence for $A$, the authors propose a novel sufficient condition of $S$ for the global identifiability of the over-complete dictionary learning problem under their formulation. This is achieved by extending the \"sufficiently scattered\" condition from non-negative matrix factorization (NMF) to the context of dictionary learning.", "weaknesses": "1) The connection between the proposed \"sufficiently scattered\" condition and the conditions outlined in [3] remains unclear. Could the authors clarify this relationship?\n\n2) The paper appears to be incomplete. For instance, the figure for the experimental section is missing, and in line 187, it seems that $\\mathcal{S} \\subseteq \\mathbb{R}^k$ should be used.", "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": "", "extra_scores": {}}, {"review_id": "ot9nd7NrEM", "reviewer": "Reviewer_BRUJ", "summary": "The paper proposes an approach for dictionary learning that uses a loss that mixes a modified, weighted version of the ell-1 norm of the mixture matrix coefficients (with different weights for different rows) with the volume of the dictionary matrix. It identifies a condition for successful identification of the mixing matrix called strong scattering. Similar to existing results, the likelihood of strong scattering for random mixing coefficient matrices such as sparse Gaussian, finding a scaling low for the number of vectors used in learning to scale like $\\mathcal{O}\\left(\\frac{k^2}{m} \\log \\frac{k^2}{m}\\right)$, where $k$ is the number of dictionary elements and $m$ is the data dimension. An alternating minimization algorithm for the proposed optimization is included as well.", "questions": "Line 165: is a square power missing outermost in the second term? Why does this line imply $\\alpha = 1$?\n\nLine 171: Why is Assumption 1 reasonable? Is this equality always possible? If so, can that be shown as a lemma?\n\nLine 188: if $\\mathcal{B}_m \\subseteq \\mathcal{S}$, then isn't $\\mathcal{B}_m \\cap \\mathcal{S} = \\mathcal{B}$?\n\nLine 246: Assumption 4 has not yet been introduced - can you move the definition earlier?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The formulation appears novel and the analytical results are comprehensive.\nA sound identifiability condition is presented.", "weaknesses": "As with other conditions for sparse learning and recovery, it appears that the required strong scattering condition cannot be efficiently checked.\n\nIt is difficult to assess how much stronger the sufficient scattering condition is versus \"that of complete dictionary learning\".\n\nSome specific arguments are not clear (see questions).\n\nA figure in the experimental section (cf. Line 466) is missing.", "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": "", "extra_scores": {}}, {"review_id": "JFoD3pkYdM", "reviewer": "Reviewer_LGHw", "summary": "This paper presents a novel  formulation for dictionary learning with the dictionary matrix being overcomplete.  Under certain conditions, the authors demonstrate that the novel formulation guarantees global identifiability on the overcomplete dictionary. Finally, the authors design  an alternating optimization algorithm to solve the proposed formulation.", "questions": "1. In Lemma 1, it seems that $\\Phi=I$ only when the optimal solution to equation 2 is unique. Hence, if there are multiple optimal solutions, does Lemma 1 still hold? If not, how to demonstrate that the optimal solution to equation 2 is unique? \n2. How to prove that $A$ in Assumption 4 must exist? In addition, note that $A$ needs to satisfy Assumption 1 as well.\n3.  In line 363, the authors state that they aim to check whether the optimal value of equation 12 equals to 1. However, Theorem 2 only gives the probability that the maximum value is greater than 1. What's the relationship between them?\n4. Are optimization problems 14 and 2 equivalent? How to determine $\\lambda$?\n5. For the synthetic experiment, using the estimation error to evaluate the algorithm's performance is somewhat unconvincing. It is more reasonable to show that there exist a permutation matrix and a diagonal matrix that can convert the learned dictionary into the real one. In addition, multiple experiments should be conducted to record the corresponding success probability.   \n6. Why didn't the authors compare the proposed algorithm with other dictionary learning algorithms in the experiment? Currently, only a simple experiment is available.\n7. Where is the Figure mentioned in line 466?\n8. Many sentences in Introduction overlap with Hu and Huang (2023a).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "It is impressive that the proposed formulation can guarantee  global identifiability over dictionary learning with an overcomplete dictionary matrix under some conditions.", "weaknesses": "1. It is not easy to verify whether $A$ and $S$ satisfy the Assumptions 3-4. Hence, it is difficult to evaluate the practical applicability of the theoretical results. \n2. The paper provides only a simple simulation experiment, and the results are somewhat unconvincing.\n2. The theoretical results are related to the optimal solution to equation 2. However, the proposed optimization algorithm for solving equation 2 cannot  guarantee convergence to a global optimum.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)