Global Identifiability of  $\ell_1$-based Dictionary Learning via Matrix Volume Optimization
Authors: Jingzhou Hu
Kejun Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: dictionary learning
matrix volume
nonconvex optimization
TL;DR: Dictionary learning is globally identifiable by minimizing the volume of the dictionary subject to  $\ell_1$ constraints.

Abstract: We propose a novel formulation for dictionary learning that minimizes the determinant of the dictionary matrix, also known as its volume, subject to the constraint that each row of the sparse coefficient matrix has unit $\ell_1$ norm. The main motivation for the proposed formulation is that it provides global identifiability guarantee of the groundtruth dictionary and sparse coefficient matrices, up to the inherent and inconsequential permutation and scaling ambiguity, if a set of vectors obtained from the coefficient matrix lies inside the $\ell_\infty$ norm ball but contains the $\ell_2$ norm ball in their convex hull. Unlike existing work on identifiability of dictionary learning, our result is global, meaning that a globally optimal solution to our proposed formulation has to be a permuted and rescaled version of the groundtruth factors. Another major improvement in our result is that there is no additional assumption on the dictionary matrix other than it is nonsingular, unlike most other work that require the atoms of the dictionary to be mutually incoherent. We also provide a probabilistic analysis and show that if the sparse coefficient matrix is generated from the widely adopted Bernoulli-Gaussian model, then it is globally identifiable if the sample size is bigger than a constant times $k\log k$, where $k$ is the number atoms in the dictionary, with overwhelming probability. The bound is essentially the same as those local identifiability results, but we show that it is also global. Finally, we propose algorithms to solve the new proposed formulation, specifically one based on the linearized-ADMM with efficient per-iteration updates. The proposed algorithms exhibit surprisingly effective performance in correctly and efficiently recovering the dictionary, as demonstrated in the numerical experiments.

Global Identifiability of l--based Dictionary Learning via Matrix Volume Optimization
Jingzhou Hu
Kejun Huang
Department of Computer and Information Science and Engineering
University Florida
Gainesville, 32611
(jingzhouhu, jejun huanguungggge Qufl.edu
Abstract
We propose novel formulation for dictionary learning that minimizes the determi- nant of the dictionary matrix, also known as its volume, subject to the constraint that each row of the sparse coefficient matrix has unit { norm. The main motiva- tion for the proposed formulation is that it provides global identifiability guarantee of the groundtruth dictionary and sparse coefficient matrices, up to the inherent and inconsequential permutation and scaling ambiguity. if a set of vectors obtained from the coefficient matrix lies inside the loo norm ball but contains the lz norm ball in their convex hull. Unlike existing work on identifiability of dictionary learning, our result global, meaning that globally optimal solution to our pro- posed formulation has to be permuted and rescaled version of the groundtruth factors. Another major improvement assumption on the dictionary matrix other than it is nonsingular, unlike most other works that require the atoms of the dictionary to mutually incoherent. We also provide probabilistic analysis and show that if the sparse coefficient matrix is generated from the widely adopted Bernoulli- Gaussian model, then is globally identifiable if the sample size bigger than constant times & log k, where k is the number of atoms the dictionary, with overwhelming probability. The bound is essentially the same those local identifiability results, but we show that it is also global. Finally, we propose algorithms to solve the new proposed formula- tion, specifically one based on the Enearized-ADMi. with efficient per-iteration updates. The proposed algorithms exhibit surprisingly effective performance in correctly and efficiently recovering the dictionary, demonstrated in the numerical experiments.
our result that there is no additional
Introduction
Dictionary learning is a famous unsupervised learning problem (ošic and Frossard 2011 that also goes by the name sparse coding [Ossaasen and Field 1997 or sparse component analysis Georgiev et al. 2005]. It stems from the intuition that samples from a data set can all be approximately represented as sparse combination of atoms from a complete or overcomplete dictionary, or x = As, for i = I,..., n. where x; E R" are the given data points, columns of A mRm represents atoms of dictionary, and s; E R are the sparse representations of x;, indicating that x; is linearly dependent only few atoms from the dictionary A with coefficients given in the nonzeros of s; Staking x; as columns of e [Rmxn and s; as columns of S Rkxn it can be written as matrix factorization model X AS. Although in some cases there exist known dictionaries that admit good-quality sparse representations, such as the DCT or wavelet basis for image compression, sometimes it is better to learn sparse-inducing dictionary from data in unsupervised fashion, hence the task of dictionary learning that tries to estimate A and jointly. In most cases, people
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

assume m S k: the dictionary is complete if m k, and overcomplete if m < k. In this paper we focus on the complete dictionary case when is square and nonsingular, which common a lot of prior works that this work is built upon [Gribonval and Schnass 2010 Sun et al. 2016a b
Wu and
Yu 2017
Wang et al. 2020
Dictionary learning has found numerous applications in signal denoising [Elad and Aharon 2006]. audio coding (Plumbley et al. 2009). and medical imaging [Tošié et 2010 name just few. On the theory side, most of the existing works have focused on algorithm design. Famous algorithms include k-SVD [Aharon al. 2006a] and online dictionary learning [Mairal et al. 2009). among numerous other algorithms based on generic nonconvex algorithm design with guarantee of convergence to a stationary point. More recently, there have appeared a line of research that attempts to show global optimality for dictionary learning under more restrictive assumptions. such as [Spielman al. 2012 Agarwal et al., 2016 Arora et al. [2014] 2015 [Sun et al. [20T6a Rambhatla et al. 2019 Bai et al. 2019 Zhai et al. 2020a b Shen et al. 2020 Tolooshams and Ba 2022].
1.1
Model identifiability
The dictionary learning problem can be considered an instance of the broader matrix factorization model X AS subject to the opaque requirement that S is sparse. It is well-known that matrix factorization without any additional assumptions on the latent factors is not unique, since we can always "insert" an invertible matrix Q and Q-1 as X = AS where cannot distinguish whether or S are the groundtruth sources. Such rotation ambiguity cannot be resolved by the well-known principal component analysis (PCA) [Jolliffe 2002].
AQ and S = Q Ss and one
On the other hand, most matrix factorization models allow scaling and permutation ambiguity, i.e.. a permutation matrix II and diagonal matrix D such that the recovered mixing matrix is ADII and the recovered sources are D S. In addition to inherent constraints that fit the application, it is sometimes helpful to have an optimization criterion in search for the "correct" factorization (up to scaling and permutation). In light of this, we formally define the identifiability of any matrix factorization model as follows:
Definition 1.1 (Identifiabilitty) Consider the generative model X A 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=4S
A
where A and S are some constraint set that A and S should belong to, respectively. If A and/or S satisfy some condition such that for any (A*,S*) there exist a permutation matrix I7 and a diagonal matrix D such that A = A DIT and S -'" then we say that the matrix factorization model is essentially identifiable, up to permutation and scaling, under that condition.
For dictionary learning in specific, where the essential constraint on the latent factors is sparsity on S, there have been some existing works on its identifiability issue. It has been shown that simply by putting a hard sparsity constraint on S is enough to guarantee a unique factorization, provided that the sample size is large enough [Aharon et al., 2006b Hillar and Sommer 2015 Cohen and Gillis 2019). The main drawback is that the required sample size n is usually too large to be practical results from [Aharon et al., (0066) and (Hillar and Sommer 2015 both require to be O((k+ + (()),, where is the number of nonzeros that each column of S is allowed have; has been relaxed to O(k3/(k =)2) by Cohen and Gillis 2019], but still very large. The existence of s in the bound also shows that an outlier sample that does not admit sparse representation from the dictionary is absolutely not allowed in the data set, which also restrictive. Inspired by the success of compressive sensing and sparse recovery, it is perhaps more common to use the L norm to approximately sparsify S. Identifiability results based on the E norm formulation has been predominantly local, meaning the model is identifiable within neighborhood of the groundtruth factors (A*, s*), but on the bright side the sample size requirement is typically down to Okk log k) and allows the existence of dense outliers [Gribonval and Schnass 2010 Wu and Yu! 2017 et al. 2020
Wang
2

---

1.2 This paper
In this paper, we intend to bridge the gap by providing global identifiability guarantee of complete dictionary recovery using a { norm based formulation, given as follows:
minimize A.S
dett
subject to X AS, ||:ll S 1.j = l,..,,
To the best of our knowledge, this is a novel formulation that has never appeared in the literature; however, we will show in the next section, the intuition stems from the more commonly used b-based formulations. We stress that the formulation is L fi-based, as the L norm is the most widely used term to promote sparsity of the solution. Although in the context of dictionary learning, using the & norm as the convex surrogate for sparsity is not enough to make the overall problem tractable, there are still benefits of using it instead of other ones such as hard sparsity constraints, for example in terms of sample complexity as introduced in the previous subsection.
After some gentle derivation to motivate the proposed new formulation we provide the following contributions:
1 for dictionary learning,
1. We give a deterministic characterization of the identifiability condition on the sparse coeffi- cient matrix S under which the dictionary (as well as the sparse coefficients) can be uniquely determined, up the inherent and inconsequential permutation and scaling ambiguity, via solving II. Unlike existing work that shows local identifiability, our result is global, mean- ing that the groundtruth factors have to be global minimizer to (I). Furthermore, perhaps surprisingly, our result only require the complete dictionary to be nonsingular- are no additional assumptions that require the atoms be mutually incoherent whatsoever.
2.
The result shows that & b-aaeed dictionary learning is globally identifiable if certain set of points, which are by definition inside the hypercube [-1, i1k, contains the unit ball in their convex hull. This geometric assumption is called "sufficiently scattered", with similar ideas appearing in pertinent unsupervised learning models. We provide intuition why this assumption generally leads to sparse S. We further show that if the sparse coefficient follows the widely used Bernoulli-Gaussian very high probability, provided the sample size n is bigger than a constant times & log(k). This is the same sample complexity bound obtained in some of the local identifiability analysis, but we show that it is also global, using the proposed new formulation (I.
generative model, then it is identifiable with
3. We propose algorithms to solve (1. specifically one based on linearize-ADDMM in the main paper; in the supplementary we also present one based on the Frank- Wolfe framework and the other based on block coordinate descent. Even though the proposed formulation (I) is nonconvex (jutt like any other dictionary learning formulation), numerical experiments on synthetic data show that they achieve global optimality in almost all cases, provided that the groundtruth latent factors satisfy the identifiabiitty assumptions given before.
2 Problem Formulation
We start by proposing novel formulation for dictionary learning. The purpose is to show that the seemingly different formulation does not come out of thin air, but is highly related, if not equivalent, to existing ones that have been studied extensively. Consider the following formulation adopted in
(Gribonval and Schnass 2010 Geng and Wright 2014, Wu and Yu 2017 Wang et al. 20200:
minimize A.S
|||||
subject
X AS, ||A 1,J I,...,k.
(2)
We use the noiseless model X = AS since the main focus of this work is identifiability, and a lot of algorithms are designed by replacing this term with loss function that measures the residual X AS. e.g. [Gribonval et al. 2015). The purpose of the f norm of is to encourage it to be sparse, but since it is also dependent on the scaling of S, the constraint ||A. < 1 is imposed onto the columns of A. Such constraints are without loss of generality due to the scaling ambiguity AS ADD-'S, Ss so for any admissible factorization, we can rescale the columns of to unit norm, while absorbing the scaling into the rows of S, without affecting the matrix product.
Due to the Lagrangian multiplier theorem, there exist positive scalars Pr...., Be and n...., Y such that any solution of the following problem is also optimal for 2
3

---

minimize A.S
Σ r
subject to X AS, AS, s Bp.J Op.== = I,..,,
since they would lead to exactly the same Lagrangian function with appropriate choices of yj and By. Again, due to the inherent scaling ambiguity, we can assume without loss of generality that βj = = I, leaving the unknown parameters to just yy's.
If we replace the summation the objective of (3) with product, or equivalently replacing the arithmetic mean with the geometric mean, the term IT YyIlA,yll would be intimately related to | det A| if A is square. Indeed, there must exist some unknown matrix G such that | det GA| I y Il. Furthermore, for the purpose of optimization it completely unnecessary to know G since det GA] | det G|| det Al, which is just a positive scaling of det A| that does not affect the optimization solution. As a result, our proposed novel formulation of dictionary learning takes the form of
Although our paper focuses on the case of complete dictionaries, i.e., when is square and non- singular, they can be effortlessly extended to the overdetermined case when A is tall, and the only modification to change the objective to det A This is sometimes called the volume of the matrix [Ben-Israe Bsrals 1992] with applications in change-of -fgrrabbl integration [Ben-Israe] [1999] and probability [een-Israel 2000 It has been used as the identification criterion for several variants of nonnegative matrix factorization with interesting geometric interpretation of finding the minimum volume enclosing simplex of a set of points (Lin et al., 2015] Huang et al., 2016 2018 Fu et al. 2018 Huang and Fu 2019]. The most related work is the polytopic matrix factorization framework proposed by Tathi and Erdogan [021], which includes a case that constraints the columns of S to have bounded e norm. Our proposed formulation constrains the rows of S, which seems to be minor difference but is in fact a great leap forward since row scaling of S is inherent for any matrix factorization, while column scaling is not. It also turns out that the identifiability analysis would be drastically different, albeit the formulations look similar.
3 Global identifiability
In this section we study the conditions under which the proposed dictionary learning formulation I is identifiable, i.c., any solution to ① equals to the groundtruth dictionary A and sparse coefficients 5 up to permutation and scaling, as per Definition 1.1 The groundtruth can have arbitrary scaling, and it is without loss of generality to assume that its rows have unit & norms; we denote such rescaled
S to be S", i.e., |15...1 1 s j.j = I,...,k; k; we absorb the counterscaling into the columns of A to generate A", so that A = =".."
Since we consider only complete dictionarics, for any feasible (A, S) for ( there must exist a nonsingular matrix W such that S ws and A A' therefore Problem (T) is, conceptually, equivalent to maximize W
det W subject to ||w") S 1, I,..,kk, k,
where w/ denotes the jth row of W. Since W = A- and A is feasible, the optimal value of (4) is at least 1. On the other hand, if the model is identifiable, then the optimal value of (4) should be exactly equal 1, and the optimal solution to 4 must be a permutation matrix times diagonal +1 matrix. The rest of this section is dedicated to characterizing when such condition holds for the sparse coefficients S. Notice that all we need for the dictionary A is that its columns are independent, so that the transform from to is possible-there is no additional assumptions such as "incoherence" for the rest of the arguments to hold, which is a great improvement to the existing works such as [Gribonval and Schnass 2010 (un et al. 2016a b Wu and Yu 2017 Wang al. 2020).
3.1 Deterministic characterization
The intuition is simple: the Hadamard inequality states that | det S II ||w))l, Il. so a sufficient condi- tion for identifiability is that the set of solutions to the following (nonconvex) quadratic programming
maximize
||maa|2
subject to ||w s

---

is Ltel,...,eey in other words, a maximizer must be an indicator vector or its negative.
To proceed, we introduce the following notion:
Assumption 3.1 (Sufficiently scattered in the hypereube). Let B denote the Euclidean ball B {x e R ||ж|| & }} and C denote the hypercube C = {xx E R || & 1). A set S is sufficiently scattered in the hypereube if:
1. B S S S C:
2. 0B n nas (+ =ek), where à denotes the boundary of the set.
A geometrie illustration of set that is sufficiently scattered in the hypercube is shown in Figure 1 which in this case is polytope with vertices depicted the hypercube [-1, i]e. but touches the boundary of [-1, 1] at points 1......, = If a set S is sufficiently scattered in [-1, 1]*, S contains 2 as a subset and, as second requirement, 2 touches the boundary of S only those points too.
dots. As we can see, B is a subset of
The term "sufficiently scattered" was first coined by Huang et al. [2016) to characterize the identifiability condition for nonnegative matrix factorization that has already appeared in (Huang et al. 2013).
The difference is that in (Huang et al. 2013 |016| Fu et al. 2018
Figure 1: An example of suffi- ciently scattered in 3D.
the condition is defined over the conic hull of a set of points in the nonnegative orthant containing specific hyperbolic cone. It has also been defined over the convex hull of a set of points in the probability simplex [Fu al. 2015 Lin et al. 2015). The most related case is the sufficiently scattered condition defined for the hypercube (fso-norm ball) (Tatli and Erdogan 2021]. as well as the standard orthoplex (e (er-norm ball).
To see how the sufficiently scattered condition could be useful for dictionary learning, we first rewrite the single constraint in (5) as, equivalently, set of 2" linear inequalities wTS v S 1, Vu (=1]". Since the rows of 5 have been rescaled to have unit e norm, we must have that ||5'v||>> s meaning that all vectors 5" v should lie in the hypercube [-1, 1] and we further assume the convex hull of all such S'v v is sufficiently scattered. Define the n x 2" matrix V that contains all elements of (=1)" " as its columns, we have the following deterministic characterization of the identifiability of T
Theorem 3.2. Consider the generative model X A'S where A e Rkxk is the groundtruth dictionary and S is the groundtruth sparse coefficients. If ra"k = k and Conv(S'V) is sufficiently scattered the hypercube as Assumption 3.11 then for any solution of (]. denoted as (A*,S*), there exist a permutation matrix and a diagonal matrix such that A A DII and S II DD- D'S In other words, dictionary learning is identifiable if the groundtruth A has full column rank and S is sufficiently scattered.
The full proof relegated to Appendix A Here we provide a concise sketch of the proof: if 5'V is sufficiently scattered, a solution to (5) must be =ey; as a result, det W I Πy ||رس||| = 1, and equality holds only if W a permutation matrix with some sign flips of its rows.
How is this assumption relevant to the sparsity of S? Notice that if SV is sufficiently scattered, then for any vector such that ||u||| < there must exist convex coefficient 0, i.e., 0 0 and ra- = 1, such that u = SVe. Due to the definition of V, we know that the vector y V0 must satisfy ll < Let us instantiate it at equals to 1. But the jth row of S has unit E norm and || S 1, so their inner product is I only if y' sign(S, J..), which is uniquely defined if sy. is completely dense. Now e, = Sy also implies the inner products between y and the rest of the rows of S all equal to zero, which is almost impossible y sign(S) SJ.) ) is the only candidate. On the other hand, if some of the entries in SJ.: are zeros, then the corresponding entries in y are free to choose any value in [-1, 1]; to make the rest of the - inner products equal to zero, we generically need at least k 1 free variables in y, meaning j contains at least k 1 zeros- it is still not guaranteed that ||yl| N 1, but it intuitively makes
ej. This means the jth row of S inner product with y
sense that the more zeros each row of S contains, the more likely that ej = Sy is feasible, which necessary for SV to be sufficiently scattered.
5

---

3.2 Probabilistic characterization
The analysis given in $3.1 gives an exact characterization of when dictionary learning is identifiable using the proposed formulation (I) with matrix volume identification criterion. However, given some sparse coefficient matrix S, checking whether satisfies the identifiability condition in Theorem 3.2 amounts to solving a nonconvex quadratic programming ( which is NP-hard in general. In this section, we assume that the sparse coefficient matrix is generated from a probabilistic generative model, specifically the Bernsulli-Gaussian model that has been widely considered in the literature, such as [Gribonval and Schnass 2010] Sun et al. [016a]] and show that it would satisfy guarantee identifiability with high probability, provided that the number of data points n is O(k log k).
R is generated from a Bernoulli- Gaussian model with parameter p (0, 1), denoted as S ~ BG(p), if its elements are i.i.d with Sij = gijgij. where bij E {0, I} are i..d. Bernoulli random variables with Pr| bij = I] = p (thus p) and gij N(0, 1) are i..dd standard normal random variables.
Assumption 3.3 Seemoulli-Gaussian model). The matrix
Pr[b,, =
Note that due to the scaling ambiguity of matrix factorization the assumption that the normal random variable has unit variance is without loss of generality- itss rows will be rescaled to have unit l norms nonetheless. What we are essentially assuming is that 1) significant portion of are zero; 2) nonzeros of S have zero mean and approximately the same variance.
Theorem 3.4. Suppose S E Reexa is generated from the Bernoulli- model BG(p), and S is obtained by scaling its rows to have unit & norm. Then
Pr
sup S
||w||| >
s 4 4xp (k log(k) - np(1 nnp - -p))
(6)
Corollary 3.5. Consider the generative model X = A'S", where A E Rkxk is the groundtruth dictionary and the groundtruth sparse coefficients. (AF) = k and the matrix S Rkxn generated from the Bernoulli-Gause
model (p),), then (A 5*) are globally identifiable via optimizing ① with probability at least 1 - exp (k log(k) np(1 - p)).
The proof of Theorem 3.4 is relegated Appendix B It is appealing to see that the presented result looks much cleaner than prior work such as [Gribonval and Schnass [010 Wu and Yu 2017 Wang al. 2020], on top of the fact that such identifiability result is global, and does not require any incoherence assumption on the dictionary. as long as it is nonsingular. An interesting observation is that most of the foundational results have appeared in the seminal work (Gribonval and Schnass
2010]; the difference is that they are used in the improved formulation (T). and in return leads to more significant result in Corollary 3.5 From the above result, we observe the following:
1.
The right- hand-side of (6) would be a valid probability (< 1) if n is bigger than a constant times & log( k)) p1 - p), and very quickly approaches zero it grows bigger. This agrees with the prior work on local identifiability that the sample complexity is of the same order (Gribonval and Schnass 2010 Geng and Wright, 2014 Wu and Yu 2017 Wang et al. 2020)_
2. The Bernoulli parameter p cannot be exactly equal to I or O. which affirms the obvious fact that S can neither be completely dense nor entirely zero The more interesting implication is that DL is identifiable (with high probability) as long as there is some nonzero probability of having zeros in
S, mater how small that probability is, provided the sample size is large enough.
4 Proposed algorithm
In this section, we propose two algorithms for the callme--opimiizatiie based formulation (T. We will reformulate ( as determinant maximization problem subject to linear constraints, and then apply the Frank-Wolfs algorithm or block coordinate descent, which are both guaranteed to converge to stationary point.
Since we assume A is nonsingular, we can define P A and apply a change of variable to problem I the objective would become minimizing 1/1 det Pl, which we apply the log function and make it log det [P], and in the constraints we can now eliminate the S variables by simply requiring |PX 1.ll1 1,j 1,...,& k. This leads to the following reformulation minimize logl det Pl
subject to ||[PX],.ll 1,j I...,k
(7)

---

Problem 7 now has a convex, or more specifically linear, constraint set, although the objective still not convex. In Appendix 4 we propose two algorithms to directly tackle this formulation, one based on the Frank-Wolfe framework, and the other is an instance of block coordinate descent. Both algorithms guarantee convergence to a stationary point, which the best one can get for a generic nonconvex problem. However, both algorithms require solving a linear programming problem in each iteration, making the overall algorithm double-looped, and the time efficiency is greatly affected by the specific subroutine solve linear programming. In the rest of this section, we propose an algorithm based on the linearized alternating direction method of multipliers (L-ADMM) with well-defined and low-complexity iterations.
4.1 Linearized alternating direction method of multipliers (L-ADMM)
We first modify the formulation 7 by introducing auxiliary variable S:
minimize P.S
log det Pl
subject to PX = ||S s 1,j = =,j= I,..,, k.
(8)
Formulation consists two sets of variables (P and S) over two separable functions (one of them being indicator function of S that the e norms of its rows are no bigger than 1) and linear equality constraints. It is easy to derive the alternating direction method of multipliers (ADMM) [Boyd et al.
2011 for
((++)) - arg min - det P
( U U
(9a)
S((t)) e arg min 11 (p/22) ((+1) X S (1)
(9b)
((+1)) - (a)) + -
(9c)
The second step (9b) is well-defined, as it projects each row of the matrix P ((+1) X + (() to the l norm ball, which can be efficiently computed with linear complexity (Duchi et al. 2008). In our implementation we use the bisection method described in (Parikh and Boyd 2014). The first step (9a), however, is not clear how to compute. One popular method to mitigate this issue, which is prevalent in ADMM, is take linear approximation of the loss function of P at the previous iterate P(r) [Lu et al. 2021]. The gradient of log | det P1 is p therefore the linear approximation of llo det P| at (()) - log det P Po) - Tr P7) (P Po ())) The overall update of P ((++)) becomes minimizing a convex quadratic function, which can be done in closed-form. The derived linearized
ADMM (L-ADMM) iterates are
P P(++)) < ((Si) - (1)) (1/P)P (1/P)
(10a)
((+1)) Projj Ilss (t+1) (n))
(10b)
U (141) (i) P ((+1)) S(+-1)-
(10c)
Finally, notice that formulation (8) and the derived L-ADMM algorithm are invariant under linear trans- formation of columns of X, meaning if replace X with X G.X in (8) where G is a k k invertible matrix, then every iterate P (z) is uniquely mapped to P G- (while (nn) and U (n) are exactly the same), and the objective value has a constant difference log det Pinl- log det G). This observation allows us to preprocess the data ma- trix X by orthogonalizing its rows, so that the update for P in (10a) can be further simplified. The overall algorithm is summarized in Algorithm| [ We empir- ically found that setting p = nk works very well in practice.
Algorithm Solving 7 with L-ADMM
I: take the QR factorization of x QR set p nk and initialize Pro)
3: for r = 0, 1, 2,., until convergence do
P(+1)) (S U Q
- llog det P G
S(++1) Proj st (P (P (1+1) +U)
U(41)) Uin ((+1) -((()))
7: end for return R-)
7

---

5
Experiments
We now provide numerical experiments to showease the effectiveness of the proposed volume optimization formulation using the two algorithms described in $ All the experiments are conducted in MATLAB.
5.1
Optimization performance
We synthetically generate random problems, and show the surprisingly effective performance of the two algorithms proposed in $ For k = 20 and n == 1000, we randomly generate the groundtruth sparse coefficient matrix S according to the Bernoulli-Gaussin model with p 0.5, and the groundtruth dictionary matrix A completely random, and generate the data matrix X = A Due to Theorem 3.4 we know it is identifiable with very high probability, despite being not that big compared to the number of atoms k. Matrix X is used as input to the I-ADMM algorithm as the global optimum Although Problem 7 nonconvex, as long as identifiable, we know attained at p = D(A))-1, where D diagonal matrix with the ith diagonal equal to the inverse of the & norm of the ith row of 5 As result, - log det D(44) is the optimal value for Problem 7 as long as the model is identifiable, and we shall see whether the proposed algorithm able attain that optimal value. On the other hand, since L-ADMM directly tackles formulation 88 it is not guaranteed that Pin) is feasible in every iteration, which makes little sense to check the difference - log det P()] + log | det P*I. We instead check the optimality gap of the Lagrangian function values, using the optimal dual variable A, since we have
described in Alg. [
log P| Tr(PX S) 2 log Pet,
for any and feasible S. Obviously, the gap equals to zero when P = p* and S = S* in which Furthermore, it is easy to show that an optimal A is ( In this simulation with known groundtruth factors, we will use this to measure the optimality gap.
10²
case p*x S*
107
gatnsty
The convergence behavior 100 random trials of the L-ADMM Algorithm [ are shown in Fig- ure The somewhat surprising observation that achieves essentially
12"
optimality gap in all instances, which somewhat surprising as we are, after all, trying to solve NP-hard problems. Among the 100 random trials, L-ADMM usually requires approximately 500-1000 iterations to converge; to- gether with the low- lowcoompexity iterations described it usually takes just few seconds to execute a trial. For a dictionary learning prob- proposed algorithm takes
124
Necoton 800 1000
Figure 2: 100 random trials of the proposed L-ADMM for dictionary learning as in Algo- rithm [ Since we know the groundtruth dictio- nary is the (essentially) unique minimizer, we can use it to calculate the optimality gap. We see that the optimality gap goes to zero in all random instances.
in Algorithm [
lem of this size, lot less time than most existing state-of-the-arts Some more detailed comparisons can be found in
the supplementary material.
5.2 Dictionary recovery
Next we fix the sample size n = 1000 and vary the dictionary size as well as the sparsity parameter in the Bernoulli-Gaussin model and check how often do we get exact recovery of the groundtruth dictionary A up to column permutation and sealing. In the previous experiment we simply check the optimality gap between the algorithm output and -log det ((A)) -1,, which is also pretty good indicator of exact recovery since the only ambiguity is an orthogonal rotation, which is very unlikely to exist. Nevertheless, to ensure definitively that the dictionary is recovered as p-1, we will normalize the column and use the Hungarian algorithm [Kuhn] 1955 to find the best column matching, and then calculate the estimation error. We declare success the estimation error smaller than 1e-5. The results are shown in Figure which agrees with the bound in Theorem 3.4
8

---

0w0.8
59
2-0.
0w0.7
57
2-0.8
0w0.5
24
240.1
A-5
1n110
h-15
k-:0
1--5 N=:00
I-:55
1-:40
1-45
I-50
Figure 3: The probability of exactly recovering the dictionary for various dictionary size and sparsity p (probability of nonzeros in S*). The sample size is fixed with n 1000.
Figure 4: Learned dictionary from a natural image.
We would like to emphasize that compared to similar figures that have appeared in the literature. the groundtruth dictionaries that we try identify are from being orthogonal, nor do we care to check whether they satisfy the incoherence assumption; moreover, the recovery is of the entire dictionary, not one of the atoms. More comparisons with some existing algorithms can be found in the supplementary.
5.3 Real data experiment
We conclude this section with a classical application of dictionary learning on image compression. For given image, it is first divided into 8 x 8 non-overlapping patches, reshaped into vector in R with 64, and stacked as columns the data matrix X. After feeding it into the L-ADMM Algorithm I the output is inverted to obtain
estimate of the dictionary A. Each column of A is then reshaped back into x patch to be shown as an atom for the dictionary. For a monochrome image with 512 x 512 pixels, it would be reshaped into data matrix X of size 64 x 4096. Thanks to the high-efficiency of the proposed L-ADMM algorithm, learning a dictionary on a data set this size takes only a few minutes from random initialization. The resulting dictionary learned from natural image is shown in Figure 4 The result agrees with most other dictionary learning algorithms, with some atoms representing edges and bright spots, while some others resemble few DCT bases.
Conclusion
In this paper we aimed answering the question of when dictionary learning is identifiable, with specific requirement that the formulation uses the l norm to promote sparsity. With novel formulation that minimizes the volume of the dictionary subject to & constraints, we close the case with affirmative yes, complete dictionary learning is indeed globally identifiable under mild conditions. Compared to similar works, our result is global, requires no conditions such as incoherence the complete dictionary, and the same time achieves the same sample complexity bound when the sparse coefficients satisfy the Bernoulli- Seroulli-Gaussian model. Finally, we propose algorithms to solve the volume optimization problem, specifically based linearized ADMM in the main paper, and demonstrate their exceptional performances on both synthetic and real data.
Acknowledgments and Disclosure of Funding
This work is supported in part by NSF CCCS-2237640.

---

References
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, and Praneeth Netrapalli. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal 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): 4311-4322 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 on Learning Theory, pages 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, pages 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.
Adi Ben-Israel. The change-of-variables formula using matrix volume. SIAM Journal on Matrix Analysis and Applications, 21(1):300-312, 1999.
Adi Ben-Isracl. An application of the matrix volume in probability. Linear Algebra and its Applica- tions, (21(1-3):-225, 2000.
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962.
Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, edition, 1999.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Jeremy Cohen and Nicolas Gillis. Identifiability of complete dictionary learning. SIAM Journal on Mathematics of Data Science, 1(3):518-533 11888566.21 2019.
John Duchi, Shai Chalev-Shwarde Yoram Singer, and Tushar Chandra. Efficient projections onto the balll for learning in high dimensions. Proceedings of the 25th International Conference on Machine Learning, pages 272-279, 2008
Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing. (((12):3736-744) 2006.
Xiao Fu, Wing-Kin Ma, Kejun Huang, and Nicholas D Sidiropoulos. Blind separation of quasi- stationary sources: Exploiting convex geometry in covariance domain. JEEE Transactions on Signal Processing, (3(9):2306-23333 2015.
Xiao Fu, Kejun Huang, and Nicholas D Sidiropoulos. On identifiability of nonnegative matrix factorization. IEEE Signal Processing Letters, 25(3):328 332,, 2018.
Quan Geng and John Wright. On the local correctness of I1-minimization for dictionary learning. In 2014 IEEE International Symposium on Information Theory, pages 3180-3184 IEÉE, 2014.
Pando Georgiev, Fabian Theis, and Andrzej Cichocki. Sparse component analysis and blind source separation of underdetermined mixtures. IEEE transactions on neural networks, 16(4):992-996 2005.
10

---

Rémi Gribonval and Karin Schnass. Dictionary identification sparse caltrix-fattorization via C 4-mminimization. IEEE Transactions on Information Theory, 36(7):3523-3532 2010.
Rémi Gribonval, Rodolphe Jenatton, Francis Bach, Martin Kleinsteuber, and Matthias Seibert.
Sample complexity of dictionary learning and other matrix factorizations. IEEE Transactions Information Theory, 61(6):3469 -348,, 2015.
Christopher J Hillar and Friedrich T Sommer. When can dictionary learning uniquely recover sparse data from subsamples? IEEE Transactions on Information Theory, 61(11):6290-6297, 2015.
Kejun Huang and Xiao Fu, Detecting overlapping and correlated communities without pure nodes: Identifiability and algorithm. In International Conference Machine Learning, pages 2859-2868, 2019.
Kejun Huang, Nicholas D Sidiropoulos, and Ananthram Swami. Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Transactions Signal Processing, 62(1):211-224, 2013.
Kejun Huang, Xiao Fu, and Nikolaos D Sidiropoulos. Anchor-free correlated topic modeling: Identifiability and algorithm. Advances 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 Machine Learning (ICML), pages 2073-2082, 2018.
Ian T Jolliffe. Principal Component Analysis. Springer, 2 edition, 2002.
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- Yung Chi, and ArulMurugan Ambikapathi. Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure- no-pure-pixel case. IEEE Transactions on Geoscience and Remote Sensing. (3(10):5530-5544 2015.
Songtao Lu, Jason Lee, Meisam Razaviyayn, and Mingyi Hong. Linearized admm converges to second-order stationary points for non-convex problems. IEEE Transactions on Signal Processing, 69:4859 4874, 2021.
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, pages 689-696, 2009.
Bruno A Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision Research, 37(23):3311-3325 1997.
Neal Parikh and Stephen Boyd, Proximal algorithms. Foundations and Trends Optimization, (3):127-239, 2014.
Gilles Pisier. The volume of convex bodies and Banach space geomelry, 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.
2009.
Sirisha Rambhatla, Xingguo Li, and Jarvis Haupt. Noodl: Provable online dictionary learning and sparse coding. In International Conference on Learning Representations, 2019.
R Tyrrell Rockafellar. Convex Analysis, volume 18. Princeton University Press, 1970.
Yifei Shen, Ye Xue, Jun Zhang, Khaled Letaief, and Vincent Lau. Complete dictionary learning via Ip-norm maximization. Conference on Uncertainty Artificial Intelligence, pages 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 Williamson, editors, Proceedings of the 25th Anmual Conference Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 37.1-37.18, Edinburgh, Scotland, 25-27 Jun 2012. PMIR.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions Information Theory, 63(2):853 -844, 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)8885-914, 2016b.
Gokcan Tatli and Alper T Erdogan. Polytopic matrix factorization: Determinant maximization based criterion and identifiability. IEEE Transactions on Signal Processing, 69:5431-5444 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, pages 5502-5505. IEEE, 2010.
Yu Wang. Siqi Wu, and Bin Yu. Unique sharp local minimum in 11 -minimizatiinn complete dictionary learning. Journal of Machine Learning Research, 21(63):1-52, 2020.
Siqi Wu and Bin Yu. Local identifiability of I I1-minimization dictionary learning: a sufficient and almost necessary condition. The Journal of Machine Learning Research, 18(1):612-6117, 2017.
Yuexiang Zhai, Hermish Mehta, Zhengyuan Zhou, and Yi Ma. Understanding ba-based dictionary learning: Interpretation, stability, and robustness. In International Conference 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 Machine Learning Research, 21 (165):1-68, 2020b.
12

---

A Proof of Theorem 3.2
The proof uses the notion of polar from convex analysis [Rockatellar 1970]
Definition A.1 (Polar set), Given set C that contains the origin, its polar set, denoted as C", is defined as
C = x & ,, E).
As an example, the polar of the unit ball 8 = [-|||||||| s 1) is itself, i.e., B B, using the Cauchy- Schwartz inequality. Due to the definition of dual norm, we also have immediately that the polar set of any norm ball is the norm ball defined by its dual norm, e.g., the tae norm ball [-1, I, 1]" the polar of the & norm ball (* |||ح||| S 1}. Given a polyhedron in the form of conv(H), i.c., the convex hull of set of vectors given the columns of H, then its polar is polyhedron in the form of linear inequalities:
conv H)) = (x H'xs
The important property the polar sets is that two sets satisfy A S 2, then 2 A which will be crucial in the sequel. The proof is not hard and can be found in standard textbooks such as [Rockafellar 1970].
Before proving Theorem 3.2 we show the following lemma as intermediate step:
Lemma A.2. conv (VV) is sufficiently scattered in the hypercube as described in Assumption 3.1 then the solution set of problem (5) [te),...,.e;]]
Proof. As explained in the main paper, the single constraint S''l11 is equivalent to set of 2 linear inequalities
w SSV S I",
where V E [=1)"x2* contains all 2" vectors {+1}" as its columns. This means w co) ie., w belongs to the polar set of conv(S'V), The sufficiently scattered condition first assumes that C conv(S"v), so conv V) _ since 8 We immediately have that any feasible for 5 must satisfy ||l||| < 1. Obviously, letting = is feasible and attains the maximum.
The second assumption is that the intersection of 0B and ô conv(S'V), V), the boundary of the two sets, the finite set (tee This, together with the first assumption, implies that for any direction not along the coordinates, there exists a point along that direction with norm strictly bigger than
I that still lie in conv(S'V), i.e., for any # = and l|yll = + e with sufficiently small e > 0,
there exists 0 E A" such that y E (Snv(S'V), Then w must also satisfy w s 1. Now consider w = y/lly we would have that ||w||| = but it's infeasible since w ||yl| This excludes any vector with norm 1 that is not in {= +ex} to be optimal for
Proof of Theorem 3.2 Consider the rescaled groundtruth factors (A'5") and an optimal solution to (A*, S*). Obviously, both of them are feasible:
x S A*S",
1S $ 1, 1111S7..11 1 j= 1,....,,k k.
Since A is invertible, we have that S* = (A*)-Ix = (A*)-1A '
Now define W = -A²
Since A is optimal for 11. have that
det A | < A
det '77 2
det W 2 1.
(11)
On the other hand, S* = W being feasible means
|| |w) 1'1l s 1, 1,..,,,,
ie.. each row W satisfies the constraint of (5). Since s'v satisfies the sufficiently scattered condition, Lemma A.2 implics that
|w S I, j L...,k. k.
13

---

As result, using the Hadamard inequality we have
det W - [ j=l
|ww|l s
(12)
and the supremum is attained when each row of W is =ej. Combining and 12 shows that det W| 1 and each row of W is =ej. Furthermore, det W| is nonzero only if none of the rows is collinear to each other, therefore W must be permutation matrix times a diagonal matrix with # on
its diagonals. This guarantees identifiability of 5 (and Ā') up to permutation and sign ambiguity, which is equivalent identifiability of A and S up permutation and scaling.
B Proof of Theorem 3.4
We assume that $ ~ BG (p), and the first thing we do is rescaling its rows to have unit & norms and use for the problem 5 To simplify the analysis, we can instead directly maximize || subject to I|w's 1111 s I, and compare it with the largest E norm of the rows of S. The complement of the intended probability can be bounded
sup
|
2
||/||| n max || 2 a S|SSI
sup
|| $1
with arbitrary choice of a. Conversely,
sup w [|] s1
||
S
sup I Shis]
||w||| a max ||S a
s
sup || 8
||w||| a + Pr max ||S
(13)
where the second inequality is obtained from the union bound. The 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 1962]:
Theorem B.1 (Bernstein's inequality). Let Za...., Zn be independent random variables with E[Z,] u2 and there exists some constant such that for all integer d
E[[Z]]] s d'v
(14)
Then
Pr
Zi - B[Z))
> $ 2 exp
2(n + cE)
Lemma B.2 (Bounding the second term in 13 Suppose S E pRkxn generated from the Bernoulli- Gaussian model BG(p). Then
max ||1l nnp 2)
npe
Pr
s 2k exp
2 V2e
Proof. Let (5......pp) Sn) be generated from BG(p), i.e., each s; b,gi with b, Beroulli with probability p and gi ~ NO, 1), we will use Bernstein's 's inequality with Z, bylg. The moments of b; all equal to p. The random variable Igil follows Chi-distribution of degree I so its moments
r d=1
Ellg/ 2d/2
(15)
((1)
For d 1 and 2 we have E[Z] PV2/ and E[Z,) p. Using the recurrence relation for the
Gamma function I(++1) = ff()) and v2/T(1/2) 2/ 7 < we can bound the rest of the moments with d
d!
B[|Z,1 11
(16)
24/2
14

---

Therefore the moments satisfy (44 with c 1/V2, results in
Pr ||s||| np(v2/p <) s Pr
Σ i=1
(Z) - -
> npe
n²pp²²
$ 2 exp
2(mp+ npe/v2)
npe2
exp
2 vīe
Finally, using the union bound
Pr max ||5 < np(v2/a - e)
s kr || np(v2/n
npe2
s 2k exp
2+ V2E
We now proceed to bound the first term in
113
First we note the following equivalence:
Pr
sup
||
>
a
Pr
inf [|]|=]
||STw|li < 1/a
(17)
|| S11
We are also going use the following notion of 8-cover from convex geometry Pisier holds for all Ep norm balls, but we are only to instantiate the Eucleadian ball:
1999 that
Lemma B.3 (8-cover). A finite ô-cover of the unit sphere in Rk is finite set Cs of points with unit l norm such that any point on the unit sphere is within away from an element in Co. i.e.
min I|w - will 6, V|[w[|| w., W,ECs
For E (0, 1) there always exists an 8-cover Ce with cardinality |Cal < (3/8)*²
Lemma B.4. Let Cs {w:) be an 8-cover for the sphere R² Assume that we have both the lowerbound
||S willi 2 V.w E Cs
and the upperbound
||ST = sup
1Stw|11 S
||
Then
inf
||STill 2 f yōvk
|
By definition of the 8-cover, for all w with unit norm we can find w, e Cs with w|w- Therefore
Proof.
|| 2 will - [[S(w - wi 2 ||S | willi
||S
th - will V 2 2 2p-
Lemma B.5 (Bounding the first term in 13 Gaussian model BG(p). Then
Suppose S |pkxn is generated from the Bernoulli-
Pr inf ||æ|||=
|S'wIli
e) 5
33
2exp
npe2
2 V2e
where 8 E (0, 1) represents any choice of 8-cover for the unit sphere.
15

---

Proof. Following Lemma B.4 we have
Pr
||Sw|] wil < ||w]lss
inf
yovk
Σ
Pr [IIS"( will <B] + Pr r].
(18)
W,ECs
where Cs is a 8-cover of the unit sphere with cardinality |Cal < (3/8)* according to Lemma
B.3
The bound the first term in (18 is almost identical to Lemma B.2 Dropping the subscript of w,. we write
||STw/li
bij Bij mj
Σ
1Z
/=1
Without the absolute value, Zz is normally distributed with zero mean and variance 0² Σ, mi
E[|Z11] = =
where G is standard normal random variable. Since x² Σj mībij Σj mj 1, we have for
2
B[[o|"] s B[lo]] = Σ m =p.
where for 1 we have
B[[ol] 2 [[lo[]= = E
Σ bi =p
Furthermore, |G] is chi-distributed with degree 1, whose moments are given in 15 so the moments of |Ze| again follows (16). Again, the moments satisfy [1 with = 1/v2, results in
Pr ||S wTl <np( 22/ e) s Pr
[2 E Z,)
npe
1=1
n² n²p²=²
S 2 exp
2(np npe/ (2)
npe2
2exp
(19)
2+ v2e
To bound ||ST]] we recall that this is the E induced norm for matrix ST which is shown to be the maximum of the E norms of the columns of S This means Lemma B.2 (but applied to the other direction) to have
use similar arguments used in
Pr |1S 11 > up(v2/x e)
Pr max || j:lll > np(v2/
Pr ||S) > np 2//x π e)
Pr Σ (2--E(Z))
npe2
> npe $ 2xxp
(20)
2 v2e
where we pick an arbitrary j [k] in the second line since this event implies that the maximum L norm of the rows are lowerbounded, and in the third line each Z; bi g:l satisfies (6). The proof is
complete by combining
18]
19 and (00 with f = np( π e) and np n)( o
Proof of Theorem 3.4 We first instantiate Lemma B.5 with
222m c)
27 c
16

---

which obviously satisfies < 1 and would also satisfies 6 > 0 if
2
E π
np
Then we have
3
3/
npe
Pr
inf [S'w/li [|]|]]
< 11/pp(
exx
2 V2e
Combining
133
and Lemma B.2 with np( v2/ E), we obtain
sup |||S||
||=||
S
inf ||t|||||
|S
1/a
Pr
max ||S
3
npe
2 k
+
exp
(21)
8
2+ V2e.
Further, with
(V31-114 1//2/xx
E<
13k11/4
where the right hand side is obviously positive, we have
2
n²p2(v2/T c)²
3 K
8 /
n² 6
We can further relax 21 to
npe2
npe²
Pr
sup
||w|| 1
2 k (k)* +1 exp
4 (k)* exp
2+ V2E!
2 V2e
|| s1
s 4exp (k log(k) np(1 ())
where in the last inequality we simply picked a small-enough e so that
2
p.
2+ V2e
This completes the proof.
C Additional Algorithms
In this section we introduce two algorithms that directly tackles the formulation repeated here:
minimize log det Pl
subject ||[PX];:ll 1, I...,k.
C.1 Frank-Wolfe algorithm
Our first attempt is to apply the Frank-Wolfe algorithm to approximately solve 7 The Frank-Wolfe algorithm, also known as the conditional gradient method for constrained optimization [Bertsekas/ 1999]. iteratively minimizes linear objective. defined by the gradient at the current iterate, under the same constraint set to determine the search direction and obtain the next iterate via some line search approach along the search direction. For the log-determinant objective in 7 we have that the gradient is -(P- As a result, the Frank-Wolfe algorithm for is given in Algorithm
Regarding the line search step, we propose to use the backtracking line search (Armijo rule) [Bertsekas 1999 to guarantee sufficient decrease of the objective function. Since the constraint set of is convex, as long as Pt)) is feasible, then P(r+)) is also feasible since it is convex combination of (()) and Pa. which are by definition feasible. Therefore, the only nontrivial part find a feasible initialization P (O) This can be done by optimizing arbitrary linear objective subject to the same
17

---

Algorithm 2 Solving 7 with Frank-Wolfe
initialize P(o P(o)
for 0, 1, 2, until convergence do
Pa arg min TT)PT) P)
subject ||[ s 1, l,...,k
a -
while - log (et(P (Pa -
-log det (() (a/2) Tr(P (t) (()) do
a t a/2
end while
P ((+1)) = P()) + a Pa - P())
end for
constraint as 7 (which means should not apply line search at this step). If A is square, there is simple initialization that works really well in our experience, by setting (0) as a diagonal matrix with
P (Oo) (c, c) = 1/1|X
i... rescaling each row of X to have unit E norm.
In terms of complexity, each iteration is dominated by the linear programming with k2 variables. Without exploiting any structure, the per-iteration complexity could be as high O(k5). However, the linear programming to be solved in Algorithm 2 is blessed with structures to be exploited to greatly reduce the complexity. Denote p; the ith row of P, then the linear programming in each iteration of Algorithm 2 is in fact & independent problems, each involving only one row of P; let f: denote the ith column of p (r) then we should solve the following problem with i l,...,
minimize P:
fiP: subject || 1.
(22)
Each of these problems involves k variables, which be solved with O(k3) flops. This important observation brings the per-iteration complexity of Algorithm down to O(k+).
Note that the Wolle algorithm is also able handle the overdetermined case when the dictionary matrix A is tall, although this case rarely considered in the context of dictionary learning: long A has full column rank, 7 can be replaced by (1/2) (P))P with its gradient equals to -(P").. Everything else follows easily.
make the change-of of variable P A", and the objective of
We implement the algorithm in MATLAB and use the built-in linprog function in MATLAB to solve each of the linear programming sub-problems (22). Dropping the subscripts in 22 the L norm constraint can be transformed as linear ones using the standard trick:
minimize p.
f'p
subject to - p t,,,s, 1,1' 1.
Using the same setting as in $5.1 but with smaller problem dimension n 200 and k 10, the convergence of 50 random trials are shown in Figure 5
C.2 Cyclic row update
Inspired by the row-separable structure of the constraint set in 7 also attempt to solve 7 via block coordinate descent-type algorithm that cyclically updates each row. However, we note that this algorithm only works when is square, unlike the Frank-Wolfe algorithm, which can be extended to the rare overdetermined case when A is tall. We will drop the log term in the objective function of when designing the cyclic row update algorithm in this subsection.
Using the Laplace's 's formula, we know that det is a linear function with respect to the ith row of P using the co-factor expansion
det P
-1)
A Pij det Pij.
18

---

optimally gap
-2
10
15
20
25
30
iteration
Figure 5: 50 random trials of the Frank-Wolfe Algorithm
2
where the matrix Pij is obtained by deleting the ith row and jth column of P. Then to apply the block coordinate descent algorithm [Bertsekas] 1 one would minimize Pl subject to ||p s 1, where f; E R is a vector defined according the co-factor expansion formula.
looks as we need to solve two linear programs for each row update, one to maximize flp; invariant under sign flip,
and one to minimize f. but notice that the constraint ||p|X|i || therefore the only difference between the solutions of the two linear programs would be a sign flip, which is both acceptable due the inherent sign ambiguity in matrix factorization and dictionary leamning in specific. Furthermore, recall that the Cramer's 's rule shows that
[P --1)+++ det Pi) det P,
meaning we can simply define fi as the ith column of p-1, and would not affect the row updates. This makes the definition of f; exactly the same way as in (22).
Algorithm 3 Solving 7 with eyclic row update
initialize P(0)) repeat
for =,...,, k do
f = p-pll el
p arg min f'p subject to ||p'X||
P
replace ith row of with p end for until convergence
The two proposed algorithms 2 and shows striking similarities, especially considering they both fundamentally solve linear programs the form of (22) in each iteration. For nonconvex optimiza- tion, both algorithms guarantees that every limit point is a stationary point with some additional assumptions, which is reassuring to know. The differences are follows:
Block coordinate descent guaranteed to monotonically improve the objective function by design, so there is no need for line search in Frank- This could save some computation as calculating det P may not be cheap when k is large.
2. On the other hand, each iteration of Frank- Wolfe only need to calculate p-1 once for the update of all its k rows, whereas cyclic row update requires to recalculate p-1 for each of its row updates. Overall, the per-iteration complexity is almost identical.
An interesting observation is that solving one subproblem 22 resembles the problem formulations in works such as (Spielman et al., 2012 Geng and Wright 2014 Sun et al. 2016a Zhai et al.) 2020b Shen et al. 2020) that attempt to find one atom the dictionary at a time in a deflation manner. The difference is that they are still trying to solve nonconvex problems, and they typically require multiple random initializations due to the risk of finding the same atoms multiple times. From different perspective, see that the benefit of using the proposed volume optimization framework provides
19

---

smartly chosen search direction given by rows of p-1 which is by definition the current iterate of the dictionary.
This algorithm is again implemented in MATLAB using the built-in 1 linprog function. Using the same setting before with the Frank-Wolfe algorithm, the convergence of 50 random trials shown in Figure 6 Comparing the two algorithms specifically, we see that Frank- Wolfe succeeds in all 50 trials, while CRU has one failure, although CRU takes much fewer number of iterations converge.
3
2.5
oplimality gap
2
1.5
0.5
0
2
3
9
10
iteration
Figure 6: 50 random trials of the cyclic row update Algorithm
D
Additional Experiments
Here provide some additional experiments to showcase the performance of the proposed volume- optimization formulation as well as the three proposed algorithms. We start by demonstrating the time-efficiency of the three proposed algorithms to motivate the use of L-ADMM the go-to method. Then we compare with some state-of-the-an dictionary learning algorithms with identifiability guarantees to showcase the improved performance of dictionary recovery by incorporating the volume criterion.
D.1 Comparing the three proposed algorithms
In Figures 5 and 6 we showed the per-iteration convergence of L-ADMM, Frank- Wolfe, and cyclic row update (i.e., block coordinate descent [BCD]) as described in Algorithm and While all three algorithms manage to obtain essentially zero optimality gap, L-ADMM takes significantly more number of iterations; on the other hand, it is obvious that the cost of L-ADMM to perform one iteration is much cheaper than those of Frank-Wolfe to the simple and efficient per-iteration update of L-ADMM, it is significantly faster than the other two proposed algorithms. We generate synthetic data sets like before, with 1000 and the sparsity level p = 0.5, and set 20 in Figure 7a and k 50 in Figure 7b Notice that both the vertical and horizontal axes are in log scale, indicating that L-ADMM several magnitude faster than the other alternatives. The difference would only become bigger as we increase n and k.
BCD. In this subsection show that, thanks
D.2 Dictionary recovery
We compare the dictionary recovery performance of the proposed volume-optimization formulation (using the L-ADMM algorithm in Algorithm I with some state-of-the-arte The most related work
are [Gribonval and Schnass, 2010 Wu and Yu 2017 Wang et al. 2020]. which focus on the local identifiability formulation (2) without proposing new algorithms. For algorithms with claimed
identifiability guarantees, the closest we find are the alternating direction method (ADM) by (unn
al. 2016a b). fa-norm maximization (f4-max) by Zhai et al. [2020b). and f3-norm maximization (f3-max) by (Shn et al. (2020). We note that ADM is not the main algorithm that is analyzed in [Sun et al. 2016a]b), but it works better and has the benefit of recovering the entire dictionary simultancously; the analyzed manifold optimization algorithm in [Sun et al. 20 b recovers the
20

---

109
10
optimally 0RB
optimaity
10
LAUMM
10
10'1
BCD
10
10
10
10
10
10
10
10
10"
time/ seconds
time / seconds
(a) 1: 20
(b) 50
Figure 7: Convergence (with respect to time in seconds) of the three proposed algorithms. In both cases n 1000 and p 0.5, and we vary the value of k. clear from both figures that L-ADMM is significantly more efficient than Frank-Wolfe or BCD.
dictionary one atom at time, which requires multiple initializations to guarantee complete recovery, and such procedures not provided by the authors on their Github page.
Note that all three baseline algorithms, ADM, 44-max, and f3-max, require that the groundtruth dictionary to be orthogonal. They claim that this is, to some extend, without loss of generality by pre-whitening the data x x. We discover that this claim is only true if the sparse coefficients matrix S follows strictly from the Bernoulli- Gaulii-a generative model, and that the sample size tends to infinity, in which case (1/n)SS' - pl: if this assumption does not hold, such pre-whitening step is not able to make an arbitrary dictionary orthogonal. As a result, when we use the same experimental setting as in $5.2 none of these algorithms are able to exactly recover the true dictionary any circumstance.
we restrict ourselves to orthogonal dictionary recovery, then we obtain some sensible results from the three baseline algorithms, although they still perform significantly worse than proposed work. What is more, even for exactly orthogonal dictionaries they are not able to recover them with very high accuracy. Here
them in two cases: In the first case shown in Tables [ and 2. we fix n = 1000 and k 20, and vary the sparsity level p from 0.1 to 0.9; in the other case shown in Tables 3 and 4 we fix 1000 and p = 0.5, and vary the dictionary size k from 5 to 50. The recovered dictionary is again permuted using the Hungarian algorithm, and then we declare successful recovery if the error is less than threshold. In each case we present two tables, one with the threshold to be 10-5 (same as the threshold used in $5.2). and the other with threshold 10-2 We see that the three baseline algorithms can provide reasonable result with the more loose threshold, especially f3-max. Regardless, the proposed volume-optimizaaion formulation with the L-ADMM, performs significantly better than all of them.
21

---

Table 1: Probability of success when fixing
1000 and k 20, threshold 10-5
p
0.2
p=
p
=
p 0.5.
0.6
p=7.7
p p=0.8
This work
0,9
0,9
ADM [Snn al. 20168
0.9
0.1
0
0
f4-max Zhai 2020p
0
0
0
0
0
0
Ey-max
Shen et al. 2020
0
0
0
Table 2: Probability of success when fixing
1000 and k 20, threshold 10-2
p =
0.1
p
p=0.3
p = 0.4
p =
0.3
p 006
p= p=0.7
p = 0.8
0.2
ADM [un al.
2016a
0.9
0,2
0
fa-max
Zhai 2020h
0
0
0
Ey-max
Shen al. 2020
0.9
0.3
0
0
0
0
Table 3: Probability of success when fixing
1000 and p 0.5, threshold 10-5
k=5
==
10
==
15
20
==
k
30
=
==
45
50
This
0.8
ADM Sun
2016a
0.9
0.6
0.2
0
0
4-max
Zhai ct 20206
0
0
0
0
0
0
0
2 m-maa
Shen et al. 2020
0
0
0
0
0
0
0
Table 4: Probability of success when fixing
1000 and 0.5, threshold 10-2
k=
==
==
k=
20
25
30
=
k=
30
This work
0.8
ADM (Sun al. 201
1
0.6
0.2
0
0
0
0
4 max
Zhai et al. 20206
0.7
0
0
0
0
0
Ey -mam
Shen et al. 2000
0.9
0
0
22


Reviews:
[{"review_id": "OmzGE1imvS", "reviewer": "Reviewer_cSox", "summary": "This paper presents a novel formulation for dictionary learning by minimizing the determinant of the dictionary matrix, subject to the constraint that each row of the sparse coefficient matrix has unit $\\ell_1$ norm. The proposed method provides global identifiability guarantees for the ground truth dictionary and sparse coefficient matrices, as long as certain conditions are met. The authors also develop an algorithm based on linearized-ADMM for complete dictionary recovery and provide a probabilistic analysis for the case where the sparse coefficient matrix is generated from the Bernoulli-Gaussian model.", "questions": "Please address the two points mentioned in the Weaknesses above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper establishes an identifiability condition on the sparse coefficient matrix and proves that $\\ell_1$-based dictionary learning is globally identifiable. This result is a significant contribution, as it extends existing work on identifiability and provides a more general understanding of the problem.\n\n2. The authors introduce an algorithm based on linearized-ADMM for complete dictionary recovery. This algorithm is an important addition to the paper, as it demonstrates a practical approach to solving the new proposed formulation.", "weaknesses": "1. A notable limitation of the paper is that the identifiability condition relies on the global minimizers of problem (1), yet the introduced algorithm cannot guarantee obtaining these global minimizers. This concern raises questions about the practical applicability of the theoretical findings, as it may not consistently converge to the desired solution.\n\n2. The paper lacks empirical evidence to support the theoretical results concerning the identifiability condition for dictionary learning. Including experimental observations that corroborate the theoretical findings would strengthen the paper and provide a more convincing argument. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive assessments. Regarding some of your concerns:\n1. *Global optimality*. Unfortunately, dictionary learning is known to be a computationally hard problem, and most existing methods that provide guarantee to a global minimizer requires some kind of \"good-enough\" initialization, which is generally hard to obtain in practice. What we find particularly encouraging is the surprisingly excellent performance of our proposed algorithm in practice, as demonstrated in $\\S5.1$ and $\\S5.2$, that it almost never fails when the sufficiently scattered condition is satisfied, even with completely random initializations. We will keep on investigating the theoretical analysis on this matter, and hopefully provide some computational guarantees for the proposed method, based on the important stepping stone in this paper.\n2. *Empirical evidence*. We intended to corroborate the theoretical findings with the experiments in $\\S5.2$, which shows the relationship between exact dictionary recovery and the sample size / sparsity level of $S$. In Appendix D.2 we also compared with some existing algorithms that claim performance guarantees, and our proposed method showed significantly better performance in *exactly recovering* the dictionary as well as the sparse coefficient matrix. Notice that the baseline methods in $\\S$D.2 fail to recover oblique dictionaries under any circumstances. They were able to recover orthogonal dictionaries to some extent, but not as effective as our method."}, {"review_id": "8hTcIAFfSp", "reviewer": "Reviewer_Jcds", "summary": "The paper studied the classic problem of dictionary learning. A new method is proposed based on optimizing the determinant of the dictionary matrix. Deterministic and probabilistic analysis are conducted for global recovery of the dictionary and coefficients.  Experiments are provided to help demonstrate the effectiveness of the method.", "questions": "## Presentation\n1. It appears that linearized ADMM is somewhat standard, so I would suggest maybe some of section 4 could be postponed, and the authors may focus more on the comments above.\n1. Multiple optimization problems (1)-(5), (7), (8) have been introduced for different purposes, some of them are equivalent, and some of them are equivalent only under certain conditions. It would be great if the authors could summarize the problems, and clarify the equivalences and purposes.\n1. In the remark below Corollary 3.5, it was said the bound works best when p is close to 0.5. Yet, Figure 3 shows that as long as p is <= 0.5. Could you comment on the cause of this apparent discrepancy? Also, you said “this agrees with empirical results in numerous works in dictionary learning”, could you cite which ones?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The formulation utilizes determinant, which is not common in the current dictionary learning literature.\nA global analysis is provided, which does not require the incoherent of the dictionary matrix.", "weaknesses": "## Novelty\nA crucial related work is Tatli and Erdogan [2021] as the authors pointed out, which studied (1) except that they bound the norm of columns of S while this paper did so for rows of S. What differs in the theoretical analysis? What differs in empirical performance? Please clarify.\n\n## Significance\n1. Lack of comparison with other dictionary learning methods\n    1. I agree that the proposed method guarantees the correctness of the global solution, which is attractive - but we do not have an algorithm provably converging to the global solution, since the problem is non-convex. On the other hand, Sun et al 2016a/b showed global convergence to a correct solution. Regardless, it would be great if one could compare theoretical results with the literature.\n    1. Moreover, it is interesting to see in synthetic experiments how the proposed method compares to baselines.\n    1. In particular, since the dictionary is only needed to be invertible rather than incoherent as per Theorem 3.2, why don’t we see some experiments where the dictionary is invertible but coherent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive assessments. Let us address some of your concerns:\n\n> **Novelty**. A crucial related work is Tatli and Erdogan [2021] as the authors pointed out, which studied (1) except that they bound the norm of columns of S while this paper did so for rows of S. What differs in the theoretical analysis? What differs in empirical performance? Please clarify.\n\nThe difference is two-fold:\n1. In terms of modeling, constraining the norms of the rows of $S$ is without loss of generality, while constraining its columns is not. As we have explained in $\\S1.1$, row-scaling of $S$ is inherent in any matrix factorization model. This allows us to consider a generative model that is intrinsically unbounded, such as the Bernoulli-Gaussian model i $\\S3.2$, and still guarantee identifiability with high probability. To the best of our knowledge, the analysis by Tatli & Erdogan [2021] is not able to provide such a guarantee for the Bernoulli-Gaussian model, since they impose the bound on the columns of $S$.\n2. The identifiability conditions are completely different. This was a little surprising to us as well. Tatli & Erdogan's condition is very intuitive: the columns of $S$ are inside the $\\ell_1$-norm ball, so they consider the largest Euclidean ball inside the $\\ell_1$-norm ball (with radius $1/\\sqrt{k}$) and requires the convex hull of $S$ to contain that. In our case, the $\\ell_1$-norm constraint is on the rows, so eventually the condition involves a different set of $2^n$ points $SV$, which lie in the $\\ell_\\infty$-norm ball, and require their convex hull to contain the Euclidean ball with radius $1$. The subsequent analysis turns out to be significantly different.\n\n> Lack of comparison with other dictionary learning methods.\n\nWe did compare with some existing methods that claim recovery guarantees in Appendix D.2. The advantage of our proposed method is very significant. Notice that in Tables 1-4, the groundtruth dictionary is in fact **orthogonal**, which is the most benign incoherence one can have, and we can still give such better performance. When the groundtruth dictionary is not orthogonal, none of the baseline methods can provide any reasonable recovery, unlike our method as shown in $\\S5.2$."}, {"review_id": "MoDDlOePX9", "reviewer": "Reviewer_Fbew", "summary": "This article proposes a new method for dictionary learning. The proposed optimisation problem minimises the determinant (volume) is derived from the l1 formulation of dictionary learning. Global identification results are proved under a general assumption of being 'sufficiently scattered'. The case of a Bernoulli-Gaussian model is also studied and recovery with high probability is guaranteed.\n\nOn the algorithmic side, the authors describe an algorithm for solving the proposed optimisation problem based on ADMM, and several numerical examples (both synthetic and real data) are presented. ", "questions": "The equivalence between the different optimisation problems is unclear to me. The main optimisation problem is (1), but the analysis consider (4) and (5). Can you clarify on why these problems are equivalent? You also use phrases such as \"conceptually, equivalent\" which I find confusing (as I'm not sure whether you actually mean equivalent). To add to this confusion, (4) and (5) seem to assume knowledge of the true factor $S^\\sharp$.\n\nIs there a relationship between the 'sufficiently scattered' condition and the incoherence conditions? It would be helpful to see a discussion on why one condition is 'better' than the other.\n\n ", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical results are impressive, as the authors establish global identifiability results without the use of the incoherence condition. ", "weaknesses": "The main concrete example is the Bernoulli-Gaussian setting, which is already covered by previous works, albeit with local guarantees -- It would be good to see more concrete examples on settings that the new framework can handle, but previous results cannot. \n\nThere are no comparisons with previous methods in the experiments section of the main paper -- it would be instructive to see comparisons with previous formulations, e.g. (2) to understand if the proposed method does have better recoverability properties, or is simply easier to analyse. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the positive assessments. Let us address some of your concerns:\n\n> There are no comparisons with previous methods in the experiments section of the main paper\n\nWe did compare with some existing methods that claim recovery guarantees in Appendix D.2. The advantage of our proposed method is very significant. Notice that in Tables 1-4, the groundtruth dictionary is in fact orthogonal, which is the most benign case one can have, and we can still give such better performance. When the groundtruth dictionary is not orthogonal, none of the baseline methods can provide any reasonable recovery, unlike our method as shown in $\\S5.2$\n\n> Equivalence of formulations (1), (4), and (5).\n\nLet us use an analogy to explain the 'conceptual equivalence' of (1) and (4). Consider the compressive sensing problem given a sensing matrix $A$ and measurements $y=Ax^\\natural$ where $x^\\natural$ is the unknown sparse vector that we want to recover. In analysis of compressive sensing works, people use the 'conceptual' formulation $\\min ||x||_1 \\text{ s.t. } Ax=Ax^\\natural$ and show that under certain conditions the optimal solution must be $x^\\natural$. The idea is similar when we say (1) and (4) are 'conceptually equivalent' in order to show that any optimal solution of (1) must be $A^\\natural$ and $S^\\natural$ up to permutation and scaling; as it is equivalent to show that any optimal solution of (4) must be a permutation matrix with arbitrary signs.\n\nOn the other hand, (4) and (5) are not equivalent. Our claim was that to ensure that any optimal solution of (4) is a signed permutation matrix, a sufficient condition is that any optimal solution of (5) is a signed coordinate vector. This is a sufficient condition, not equivalent.\n\nWe hope this clarification is helpful :)\n\n> Is there a relationship between the 'sufficiently scattered' condition and the incoherence conditions?\n\nNo. For the dictionary learning model $X=AS$, incoherence is a condition on $A$, while sufficiently scattered is a condition on $S$. Our claim is that DL is globally identifiable if $S$ is sufficiently scattered and $A$ is full rank. Prior work shows that DL is *locally* identifiable if $A$ is incoherent and $S$ follows some probabilistic model such as the Bernoulli-Gaussian model. Overall, our result has a more relaxed condition on $A$ (invertible vs. incoherent), a more relaxed condition on $S$ (sufficiently scattered, which can be implied by the Bernoulli-Gaussian model as we showed in $\\S$3.2), and a stronger guarantee (local vs. global)."}]

Author rebuttal:

Meta-review: The paper develops a novel formulation for complete dictionary learning based on determinant minimization. This formulation seeks a dictionary matrix A and coefficient matrix S such that the observed matrix X = AS, the rows of S have small L1 norm, and A has small determinant. This determinant regularization helps the authors to prove global uniqueness of the dictionary (up to signed permutation), with no requirement of incoherence, and near optimal rates in random models. [Determinant regularization may also have practical advantages for regularizing the reconstruction problem when the data are nearly degenerate, a common occurrence in practice]. The paper provides theoretical guarantees of identifiability and a practical algorithm based on alternating directions method of multipliers which, while not guaranteed, is shown to be effective in experiments. 

Reviewers provided a generally positive evaluation of the paper, expressing appreciation for the paper’s theoretical contributions (identifiability without incoherence, optimal rates). Points of discussion included the lack of a global algorithmic guarantee, effect of incoherence and conditioning, and implications of the experiments. After considering author responses, the reviewers converged to a consensus to accept; the AC concurs and recommends acceptance based on the paper’s novel formulation and theory.
Decision: Accept (poster)