Understanding l4-based Dictionary Learning: Interpretation, Stability, and Robustness
Authors: Yuexiang Zhai
Hermish Mehta
Zhengyuan Zhou
Yi Ma
Venue:  (2020)
Keywords: L4-norm Maximization
Robust Dictionary Learning

Abstract: Recently, the $\ell^4$-norm maximization has been proposed to solve the sparse dictionary learning (SDL) problem. The simple MSP (matching, stretching, and projection) algorithm proposed by \cite{zhai2019a} has proved surprisingly efficient and effective.  This paper aims to better understand this algorithm from its strong geometric and statistical connections with the classic PCA and ICA, as well as their associated fixed-point style algorithms. Such connections provide a unified way of viewing problems that pursue {\em principal}, {\em independent}, or {\em sparse} components of high-dimensional data. Our studies reveal additional good properties of $\ell^4$-maximization: not only is the MSP algorithm for sparse coding insensitive to small noise, but it is also robust to outliers and resilient to sparse corruptions. We provide statistical justification for such inherently nice properties. To corroborate the theoretical analysis, we also provide extensive and compelling experimental evidence with both synthetic data and real images.

Published as a conference paper at ICLR 2020
UNDERSTANDING -BASED DICTIONARY LEARNING:
INTERPRETATION, STABILITY, AND ROBUSTNESS
Yuexiang 2h Hermish Mehta
Zhengyuan Zhou?
Yi Ma'
Department of EECS, UC Berkeley
ByteeDance Inc.
Stern School of Business, NYU
ABSTRACT
Recently, the -ooor maximization has been proposed solve the sparse dictio- nary learning (SDL) problem. The simple MSP (matching, stretching, and pro- jection) algorithm proposed by Zhai al. (2019a) has shown to be surprisingly efficient and effective. This paper aims to better understand this algorithm from its strong geometric and statistical connections with the classic PCA and ICA, as well as their associated fixed-point style algorithms. Such connections provide a uni- fied way of viewing problems that pursue principal, independent, or sparse com- ponents of nigh-dimensional data. Our studies reveal additional good properties of e mm-maxmization: not only is the MSP algorithm for sparse coding insensitive to small noise, but it is also robust to outliers and resilient to sparse corruptions. We provide statistical justification for such inherently nice properties. To corroborate the theoretical analysis, we also provide extensive and compelling experimental evidence with both synthetic data and real images.
INTRODUCTION
The explosion of massive amounts of high-dimensional data has become the modern-day norm for a large number of scientific and engineering disciplines and hence presents a daunting challenge for both computation and learning. Rising to this challenge, sparse dictionary learning (SDL) provides a potent framework in representation learning that exploits the blessing of dimensionality: real data tends to lie in or near some low-dimessional subspaces dimension is often extremely large (e.g. the number of raw pixels in an image). More specifically, SDL (Olshausen & Field (1997); Mairal et al. (2008; 2012; 2014); Spielman al. (2012); Sun al. (2015); Bai et al. (2018); Qu et al. (2019)) concerns the problem of learning compact, sparse representation from raw, unlabelled data: given data matrix Y [y1. y2..... ............ ypl E R=*p that contains p n-dimensional samples, one aims to find linear transformation (i.e. dictionary) D e
manifolds,
though the ambient
Raxm and an associated maximally sparse representation X [21,, .., Fpp] RRmxp that satisfies
DX.
(I)
As the data matrix Y represent variety of signals (e.g. images, audios, languages, and genetics etc) in practical applications, SDL provides a versatile structure-seeking formulation that has found widespread applications in computational neuroscience, image processing, computer vision, and machine learning at large (Olshausen & Field, 1996; 1997; Argyriou et al., 2008; Ranzato et al., 2007; Elad & Aharon, 2006; Wright et al., 2008; Yang et al., 2010; Zhang et al., 2013; Mairal al., 2014: Zhang et al., 2014: 2019).
Related Works. Motivated by this practical significance, there has been growing surge of interest recently (e.g. Rambhatla al. (2019); Bai et al. (2018); Gilboa al. (2018); Nguyen et al. (2018); Chatterji & Bartlett (2017); Mensch et al. (2016)) that aims to tackle SDL. In attempts to recover the sparse signals X, these existing work adopt an e"- or L e'-penalty function to promote the underlying sparsity and give various optimization algorithms for the resulting objectives (some of those are heuristics while few others have theoretical convergence guarantees). Although these penalty
WWor done when interning at ByteDance. YZ would like to thank Chong You at UC Berkeley for mean- ingful discussions. Correspondence to: Yuexiang 7hai, ysz@herkeley.cee or Yi Ma, yima wew@@eeecssseeeee herkeeeele......... Codes available https: /gtittb..t.....o com hwwr/eerreeeeeeeeeeeee///e sh/ /MMM- 2.2.0

---

Published as a conference paper at ICLR 2020
functions are indeed spursity-promodiee the resulting optimization problems must be solved one row at a time, hence resulting as many optimization problems as the ambient dimension n. Consequently, e or l' -based objectives result only in local methods (i.e. cannot yield the entire solution at once) and hence entail prohibitive computational burden. Another prominent approach in SDL is Sum- of- of-Squares (SOS), proposed by and articulated in series of recent work (Barak al. (2015); Ma et al. (2016); Schramm & Steurer (2017)). The key idea there is to utilize the properties of higher order SOS polynomials to correctly recover one column of the dictionary at time, for which there are m columns in total. However, the computational complexity of these recovery methods are quasi-polynomial, thus again resulting in large computational expense.
Very recently, in the complete dictionary learning' setting, a novel global approach has been sug- gested in Zhai et al. (2019a;h) that presents a formulation which can efficiently recover the sparse signal matrix X once and for all. In particular, Zhai et al. (2019h) has shown that if the generative model for Y = X E RRxx satisfies that D, E (n; IR) is orthonormal and X. E TRxx Bermoulii-Gausiiann sparse," then maximizing the -normm of AY over Onn;
max 7 |AYII subject to AE O(;; R) (or AA" = I),
able to find the ground truth dictionary D, up to an arbitrary signed permutation. Moreover, Zhai et al. (2019b) has proposed the simple "Matching, Stretching, and Projection" (MSP) algorithm, which is shown to be experimentally efficient and effective, for solving the program in equation 2:
MSP:
Ar+1 = Po(m:) ((AY) " y = U,V,
where U, V are from the singular value decomposition: U, V (AY)
In this paper, we here give an alternative (arguably simpler and more revealing) derivation of the MSP algorithm (3). Consider the Lagrangian formulation of the constrained optimization problem
given in equation 2. The necessary condition of critical points, V AY || = V (A, AA" I) for some Lagrangian multipliers A, implies:
(A (A + AA)A')A
(4)
As the optimization is over the orthogonal group O(n; IR,, restricting the condition in equation onto the orthogonal group yields a necessary condition for any critical point A:4
Po(n:)) ((AY) ( A.
Hence the critical point A can be viewed as a "fixed point" of the map: Po(m;R) (((-)))(8)) from (n;; R) to itself. The MSP algorithm in equation 3 is to find the fixed point(s) of this map.
Notice that the orthonormal constraint A E ((;; R) in equation 2 can be viewed as enforcing the orthogonality of n unit vectors simultaneously. So, more flexibly and generally, one may choose to compute any k for < n, leading orthonormal bases of D, by solving the program:
max- | subject to W St(n, R; C BRn
(6)
where St(n, k; R) is the Stiefel manifold." 5 The orthogonal group O(n; RR) and the unit sphere S can be viewed as two special cases of the Stiefel manifold St(n,, k; RR,, with k = n and A = 1, re- spectively. In some specific tasks such as dictionary learning and blind deconvolution, optimization over the unit sphere has been widely practiced, such as in Sun et al. (2015); Bai et al. (2018); Zhang al. (2018); Kuo et al. (2019). The more general setting of maximizing convex function over any compact set also has been studied by Journée et al. (2010) in the context of sparse PCA, which has provided convergence guarantees for this class of programs.
'Comleete dictionary learning requires the learned dictionary D in equation to be square and invertible. 2 'ach entry 24,5 of X can be represented as the product of Bernoulli variable and a normal Gaussian variable: Ti.j 2i Vi.j. where Ri, resd Ber(() and Vi. red (N, 1), similar for vectors scalars. This the standard setting adopted in Spielman et al. (2012); Sun et al. (2015); Bai et al. (2018).
We abuse the notation a bit, by denoting I1-11, as the sum of element wise 4th power of all entries of a vector and matrix, that is, Va E R", ||a]]] = >i= a and V.A E 2==
|| Σ,, ai,--
*For any symmetric matrix S E R=** and an orthogonal matrix E O RR), the projection of S A onto
the orthogonal group is A: Po( [SA] = A. one may see Absil & Malick (2012) for details.
Forr any 1 <
St k R = [ E n W
Iz].
2

---

Published as a conference paper at ICLR 2020
Our Contributions. Our contributions twofold. First, by taking suitable analytical angle, reveal novel geometric and statistical connections between PCA, ICA and the - maximization based SDL. We then show that algorithm- wise. the fixed-point type MSP algorithm for -orm maximization has the same nature as the classic power-iteration method for PCA (Jolliffe, 201 and the FastICA algorithm for ICA (Hyvärinen & Oja, 1997). This interpretation gives unified view for problems that pursue principal, independent, or sparse components from high-dimensional data and enriches our understanding of low-dimensional structure recovery frameworks, classical and new, at both formulation and algorithmic fronts.
Second, and more importantly from practical perspective, we examine how MSP performs under a variety of more realistic conditions. when the measurements Y could be contaminated with noise, outliers, or sparse corruptions. We show that, similar to PCA, et-norm maximization and the MSP algorithm are inherently stable to small noise. Somewhat surprisingly though, unlike PCA, the MSP algorithm is further robust to outliers and resilient to sparse gross errors! We provide character- izations of these desirable properties of MSP. The claims are further corroborated with extensive experiments on both synthetic data and real images. Taken as a whole, our results contribute to the broad landscape of dictionary learning by affirming that L mmmaximizattion based SDL and the corresponding global algorithm MSP provide a valuable toolkit to the existing literature.
SDL VERSUS PCA AND ICA
2. PURSUIT OF PRINCIPAL, INDEPENDENT, SPARSE COMPONENTS
Relation with the Geometric Interpretation of PCA. For a data matrix Y E RTxp, Principal Component Analysis (PCA), aiming to find the top (top k)) left singular vector (vectors) of Y.
max W
W
"I subject to W E St(n, k; R),
(7)
2
can be understood as finding a direction (a k-dimensional subspace) in row(Y) in which Y has the largest (2-norm (Frobenius norm). For instance, finding the direction with the largest (2-norm over the unit sphere can be viewed as calculating the spectral norm (or the largest singular value), of matrix Y. In comparison, we may view equation
WY subject to W E St(n, k;; W
max
finding direction, a k-dimensional subspace, in row(Y) Y) where the projection of Y has the largest no-mm. For instance, finding the direction with the largest (o-morm over the unit sphere (equation 6) can be viewed calculating the induced |1-1|2,4 norm of matrix Y: || = max |a Y
Relation with the Statistical Interpretation of PCA. View each column yj.j E [p] of data matrix Y gaxp as an n dimensional random vector that is i.i.d. drawn from a distribution of random variable y and let Y. denote the centered Y: Y. Y[I 1111), where 1 E R² is vector of all I's. Then, finding the top k principal components of Y:: max.est(..e3)) 2 ||W'Y is to find k uncorrelated projections of E TR" that has the top k sample variance (i.e. 2nd order moment) (Jolliffe, 2011; Helwig, 2017). Similar to PCA, the 8 -orm maximization centered data matrix Y:: maxwesk(n.ke that have the top k sample 4hh order moment, whose statistical meaning is better revealed below.
| can be viewed as finding k uncorrelated projections of y
Relation with ICA and Nonnormality. The - maximization over the Stiefel manifold is strongly related to finding the maximal or minimal kurtosis in Independent Component Analysis (ICA) (Hyvärinen Oja, 1997; 2000): order identify one component of given random vector E R", ICA aims to find a unit vector (a direction) a E g that maximizes or minimizes the kurtosis of w" y. defined as:
(8) Kurtosis is widely used for evaluating the nonnormality of random variable; see DeCarlo (1997); Hyvärinen & Oja (1997; 2000). According to Huber (1985), the nonnormality of data carries "ab- normal" hence interesting information in real data for many applications (e.g. Lee al. (2003); Cain
kurt(w" y) = (w"y)' y)² 33 3//11
3

---

Published as a conference paper at ICLR 2020
et al. (2017)). Thus, extracting the 4th order moment helps understand such statisties of real datasets (Hyvärinen et al., 2009) and even their topology (Carlsson, 2009). One may also find that the e*- maximization based dictionary learning formulation is similar to maximizing kurtosis (equation 8) with spherical constraint to E @ in fact, these two formulations are exactly the same one only wants to find one column of the dictionary. Intuitively, such coincidence occurs due to the fact that maximizing e -noom or kurtosis have the same effect- they both promote the "spikiness" (Zhang al. (2018); Li & Bresler (2018)) (or "peak" (DeCarlo, 1997)) of distribution. More rigorous analysis regarding the similarity between e ---aeeed dictionary learning and ICA is beyond the scope of this paper and we leave them for future research.
2.2 POINT STYLE ALGORITHMS
In optimization, the -orm maximization in equation over the Stiefel manifold St(k, n; R) is special type of nonconvex optimization problem convex maximization over a compact set. Al- though Journée et al. (2010); Zhai et al. (2019b) have shown that the MSP algorithm guaranteed to find critical points, the experiments in Zhai et al. (2019b) suggest that the MSP algorithm finds global maxima of the (o-morm efficiently and effectively. For better understanding. this section illustrate some striking similarities between the MSP algorithm and the "power-iteration" type algorithms for solving PCA as well as ICA.
Fixed-point pointpoint Perspective Power Iteration. For general data matrix Y E R=xp, finding the top singular value of Y is equivalent to solving the following optimization problem:
max (ww) w 2I
subject to w E S"-1
(9)
For this constrained optimization, the Lagrangian multiplier method gives the necessary condition: Vw-p(w) YY" w Xw, similar equation 4. If we restrict this condition onto the sphere, we obtain the fixed point condition ur Pgn V (w))) The classic nower-iteration method
= YY wi
Wi+1 = Pgn
V [w
(10)
|YY=w,ll2
is precisely computing this fixed point, which is arguably the most efficient and widely used algo- rithm solve equation 9, for PCA (or computing SVD of Y).
fixed-point Perspective of FastICA. In order to maximize (or minimize) the kurtosis over Sn-1
1 TE /wr" y)²
3
max (w)) = -kur(ww" y]
w subject to E S
(11)
4
4
4
Hyvärinen & Oja (1997) has proposed the following fixed-point type iteration:
R.
(v m: )"] 3 m0
W Ppg-- [ww)]
(12)
y (, 3 w. w.
which enjoys cubic (at least quadratic) rate of convergence, under the ICA model assumption.
Fixed-point Perspective of MSP. For the -t-orrm maximization program:
1 I subject W St(n,, K),,,
max e W)
through a similar derivation to that Section one can show that the MSP iteration in equation for the orthogonal group generalizes the Stiefel manifold case
W W++ (st(,,A;)) (wo(W,) U.V."
(13)
The above iteration has the same nature as the power iteration in equation 10 and equation 12, since they all solve fixed-point type problem, by project- ing gradient of the objective function V.)(), T)) Vw(-) onto the constraint manifold $ and St k; R), respectively. Table summarizes these striking similarities.
where V. SY
4

---

Published as a conference paper at ICLR 2020
Objectives
Constraint Sets
Algorithms
Power Iteration yF ((w) = : 1| 2
E 3a-1
Wt+11 Sa 1 [wo)(wr))
FastICA
(w) = kurt w y
E g
Wh+1 Pgn-1 (V (ww))
MSP & (W) |
W E kt(n,
W441 Pst(n..::)) (w W.)]
Table Similarities among fixed-point algorithms for Power Iteration, FastICA, and MSP.
3 STABILITY AND ROBUSTNESS OF e -NOM MAXIMIZATION
Even though the MSP algorithm for e'-morm maximization is similar to power-iteration for PCA, in real applications, PCA often requires modifications to improve its robustness (Candès et al., 2011; Xu al., 2010; 2012). In this section, want to examine the stability and robustness of the e4 maximization for different types of imperfect measurement models: small noise, outliers, and sparse corruptions of large magnitude.
3.1 DIFFERENT MODELS FOR IMPERFECT MEASUREMENTS
We adopt the same BernouliiGGausiaa model as in prior works (Spielman et al., 2012; Sun et al., 2015; Bai et al., 2018; Zhai et al., 2019b) to test the stability and robustness of the mmmmxmmizatioon framework. Assume clean observation matrix Y E _xxx is produced by the product of a ground truth orthogonal dictionary D. and a Bernoulii-Gause
matrix X. E R"Kp:
Y D.X.: D. E On;; R), (Xo)i, Rad BG(
(14)
Now let us assume we only observe different types of imperfect measurements of Y:
Noisy Measurements: Yv := +GG. where G 12*x is matrix that satisfies grjj aid N(0
and 1) > 0 controls the variance of the noise.
Measurements with Outliers: Yo |Y, G"), where Yo contains extra columns (G' E Roxtpp6 generated from an independent Gaussian process Sh,j wad (0, 1). Here, T controls the portion of the outliers w.r.t. the clean data size p.
Measurements with Sparse Corruptions:
where controls the scale of corrupting entries," B E RTxp is a Bernoulli matrix so bi.j mis Ber(3) with 3 E (0, 1) controlling the ratio of the sparse corruptions, and S E Raxp has entries 8t. drawn i.i.d. from Rademacher distribution:
with probability 1/2 with probability 1/2
$i.
-11
(15)
3.2 STATISTICAL ANALYSIS AND JUSTIFICATION
The analysis for the stability and robustness of the e -norm maximization follows similar statistical analysis techniques in Zhai et al. (2019b) to show that the global maximum of
W. E arg max E I Y.
subject to W E On)
(16)
satisfies W:D. E SP(n).* Note here Y. denotes different imperfect measurements: noisy (Yv),, with outliers (Yo), and with sparse corruptions (Yc). Below we provide the expectation and con- centration results for || |W Y. over the data distribution. We show that E || Y. l1 is largely determined by D. a quantity that indicates a "distance" from W D. to SP(n). As shown in Lemma 2.3 and Lemma 2.4 in Zhai et al. (2019b), the only global maximizers of [ Dolll are signed permutation matrices, and W D, converges to signed permutation matrix as W D reaches its global maximum.
'In case 7p not integer, we round Tp to the closest integer.
In our context, o = 1 is already corruption of large magnitude, since the variance of the sparse signal is 1. *SP(n) is the signed permutation group, group of orthogonal matrices that only contain +1
5

---

Published as a conference paper at ICLR 2020
Proposition 3.1 (Expectation of Objective with Small Noise) 40 (0.1), let Xo Ruxp, Fişj aid B) Let D. E ( R) be an orthogonal matrix and assume Y = DoXo For any orthogonal matrix W E On;; RR and any random Gaussian matrix G TRxxx, 9t. midd NO, n²²) independent of Xo. let YN Y + G denote the data with noise. Then the expectation of
1 I YN I1 satisfies:
up
[ n
Dollá Co.
EX..G [ 30(1
(17)
nop
where Ce,n is constant which depends on I and n.
Proof See Appendix A.1.
Theorem 3.2 (Concentration of Objective with Small Noise) Ao E (0,1), let Xo E Ruxp,
Fijj Mid BG( Let D. E O R) be orthogonal matrix and assume Y DoXor For any orthogonal matrix W E Om: R) and any random Gaussian matrix G E IRxp 99.5 wid (O,
independent of X let YN Y + G denote the input with noise, then:
1
1
P sup WcO(m:) Tpp
W'YN E Y 26 <
(18)
p
when p- ((1 + n"² ln)/
Proof See Appendix A.2.
Proposition 3.3 (Expectation of Objective with Outliers) 4A E (0. 1). let X. RRXP, Fij Mid
BG( Let Do E O(n; R) be an orthogonal matrix and assume Y D.X.- For any orthog- onal matrix W E O(n; R) and any random Gaussian matrix G' E BTXTP, 9'g Wid ((0,1) 1) independent of X let Yo (Y,G)) denote the data with outliess G'. Then the expectation of (/WYYol;s 4 satisfies:
1 Ex,,G' [ 30(1 -0) W' np
+ Co.
(19)
where Co,- is a constant depends on 0 T.
Proof See Appendix A.3
Theorem 3.4 (Concentration of Objective with Outliers) VA E 1), let X, E Buxp, Ftf rid BG) Let Do (n; R) be an orthogonal matrix and assume Y = DoXo For any orthogonal matrix W E Om; R) and any random Gaussian matrix G' E RnxTp, Iig aed N(0. 1) indepen-
dent of X., let Yo Y G') denote the input with outlier G², then:
P sup 1 W
E EI -
Yoll 28
<
1
(20)
Weo(m:) nip
when p n22 In n//2
Proof See Appendix A.4.
In the above results, Proposition 3.1 and 3.3 reveal that both normalized LE WE Y, || LE ('W'Yoll are only determined by | Moreover, shown in Theorem 3.2 and 3.4, when p is large enough 2((1 * In n),, 2n In n) respectively). both up I Yv lld. mp W Yol! 1 concentrate around their expectation with high probability. Therefore, the norm maximization formulation W.Y.ll, || for dictionary learning is insensitive dense Gaussian noise and robust to Gaussian outliers."
np
up
'I the outlier case, Proposition 3.3 and Theorem 3.4 can be generalized to any rotation invariant distribu- tions, e.g., uniform distribution the sphere. More details regarding rotation invariant distributions can be found in Chapter of Bryc (2012).

---

Published as a conference paper at ICLR 2020
Proposition 3.5 (Expectation of Objective with Sparse Corruptions) 40 E (0,1), let X RTXP, Fig riii (G Let Do E (n; R) be an orthogonal matrix and assume Y = DoXo. For any orthogonal matrix W E On; IR) and any random Bernoulli matrix B E RuxP Dis ridd (er independent of X let Ye = Y + o B o S denote the data with sparse corruptions, and S E "R" is defined in equation 15. Then the expectation of 1 np |W'Ylll' satisfies:
|W Doll n
[WIl ll
Top B,,, W 30(1 -
+ + 1213(333)) 33)
+ Co...
(21)
where C is constant depending on 0, and B. Proof See Appendix A.5.
Theorem 3.6 (Concentration of Objective with Sparse Corruptions) v0 E (0, let Xo ReXP, Fig Widd BG( Let D. E (n; R) be an orthogonal matrix and assume Y DoXo For any orthogonal matrix W O(; R. and any random Bernoulli matrix B E Rnxp ,b.. Widd Ber(B) (8) independent of X.. let Yc = + o S denote the input with sparse corruptions, and S E RRx is defined in equation 15, then:
P
sup R)O(m:))
WEI 28 p
(22)
np
when p- = O (o 3n lnn/6))
Proof See Appendix A.6.
Unlike the cases with noise and outliers, Proposition 3.5 and Theorem 3.6 indicate that ap Y depends on both l|W* ll and ||W]l when p = l( 2("*3nn" In,,, the objective W> Yelld concentrates around this expectation with high probability. Nevertheless, when the magnitude of o *3(1 3.3) is significantly smaller than 30 - -), the landscape of the objec- tive | would largely be determined by || W Doll' only. As shown in Figure 1, this indeed the case whenever: (a) the sparsity level 0 of ground truth signal X is "reasonably" small (neither diminishing to nor larger than 0.5):(b) 3, the sparsity level of the corruption, is small (smaller than 0.5); (c) the mag- nitude of the sparse errors, is not significantly larger than the in- trinsic variance of the sparse signal (the intrinsic variance of the sparse signal Hemoulli-Gaussian model is 1).
08-
07
08
0.
0.3
8.1
Figure 1: Comparison between 3x(1 - x) and y/ a² |xx(1 3r) when x E [0, 1] with different
y
Therefore, besides the insensitivity to small noise and robustness to outliers, the mm-aimmizatioon based dictionary learning also shows resilience to sparse corruptions under reasonable conditions.
4 SIMULATIONS AND EXPERIMENTS
4.1 QUANTITATIVE EVALUATION: SIMULATIONS ON SYNTHETIC DATA
Single Trial of MSP. In this simulation, we run the MSP algorithm from equation 3, using the imperfect measurements Y. of different models (Yn: Yo, Yc). As shown in Figure 2, the normal- ized value of WV-D.ll /n reaches global maximum with all types of inputs when varying the level of noise, outliers, and sparse corruptions. Moreover, as the scale of imperfect measurements increase, Figure 2 shows that (a) the iterations for convergence increases and (b) the final objective
value || Doll: decreases almost negligibly. This numerical experiment suggests that the MSP algorithm is able to identify the ground truth orthogonal transformation D, despite different types of imperfect measurements.
Phase Transition. Next, we conduct extensive simulations study the relation between recovery accuracy and sample size We run the experiments by increasing the sample size p w.nt. the scale of imperfect measurements n, F, B, respectively. As shown in Figure 3, the MSP algorithm (3)
7

---

Published as a conference paper at ICLR 2020
1.-
(iuies Cor aien Kilied Dipers Carr diicn
08
0
(c) m = 50, p = 20, 20,000,,6 A= 0.3, (a) n1 = 50, p = 20, 000, = 0.3, (b) = 50, = 20, 000, 0 = 0.3,
varying 7² from 0.1 to 0.4
varying from 0.1 to 0.4
1, varying /3 from 0.1 to 0.4
Figure 2: Normalized W D. /n of the MSP algorithm for dictionary learning, using imperfect measurements YN, Yo, Yo, respectively.
demonstrates a clear phase transition behavior w.r.t. noise, outliers, and sparse corruptions. Such phenomena suggest that the algorithm inherently stable and robust to certain amounts of noise, outliers, and sparse corruptions. The results corroborate our concentration results in Theorem 3.2, 3.4 and 3.6- larger sample size p increases the accuracy and robustness of the MSP algorithm (3) for all types of nuisances.
55
33
A7
96
66
02
(VVilonno Nccee
-Doullur
|Soake StmpllerPaak
(a) Noise: = 50, 0 0.3
(b) Outliers: n 50,0
0.3
(c) Corruptions: = 50,0 0 = 0.3
Figure 3: Average normalized error |1 W Dolla /n| of 10 random trials for the MSP algorithm: (a) Varying sample size and variance of noise y)²; (b) Varying sample size and Gaussian Outlier ratio r; (c) Varying sample size and sparse corruption ratio B, with fixed
Comparison with Prior Arts. We also compare the MSP algorithm (Zhai al., 2019b) with pre- vious complete dictionary learning algorithms: Subgradient (SG) (Bai et al., 2018) and Riemannian Trust Region (RTR) methods (Sun al., 2015). While SG and RTR demonstrate slightly better accuracy in some cases (c.g. small Gaussian noise and Gaussian outliers), both algorithms appear unstable sparse corruptions. Meanwhile, the MSP algorithm is stable to all imperfect measure- ment models mentioned in this paper and runs significantly faster than the others.
Clean
Noise
Outlier
Compptiin
0.2
0.1
Alg.
Exror
Time
Eiroor
Time
Etror
Time
Error
Time
Ervor
Time
Error
Time
Error
Time
25
10k
MSP
0.34%
1.146
0.45%
1.11s
0.99%
1.12s
1.11%
1.29
1.82%
1.45s
1.27%
1.05s
2.85%
1.03s
0.00%
8.00m
5.54%
19.3m
25.7%
26.4m
0.00%
9.62m
0.00%
11.1m
87.0%
16.6m
88.4%
34.2m
RTR
0.00%
3.28m
0.03%
17.0m
1.34%
20.2m
0.00%
4.63m
0.00%
5.87m
3.20%
18.0m
33.9%
16.3m
20%
0.47%
4.65s
1.02%
5.44s
1.15%
6.45%
1.33%
4.41s
SG
0.00%
1.34h
N/A
>-2h
N/A
2-2h
3.42%
1,40b
0.00%
1.81h
N/A
>-2h
N/A
>2hh
RTR
0.00
23.0m
0.04%
1.57h
1.65%
1.38h
0.00%
30.7m
0.00%
41.8m
2.17%
1.25h
82.57%
1.29h
Table 2: Comparison the MSP algorithm (Zhai et al., 2019b) with prior complete dictionary learning algorithms: Subgradient method (Bai al., 2018) and Riemannian Trust Region (Sun et al., 2015) methods different models with fixed ground truth sparsity = 0.3. Note that SG only learns unit vector each time and does guarantee orthogonality; we therefore project the dictionary learned to O(n; R) for fair comparison.
8

---

Published as a conference paper at ICLR 2020
4.2 QUALITATIVE EVALUATION: EXPERIMENTS ON REAL IMAGES AND PATCHES
Besides simulations, also conduct extensive experiments verify the stability and robustness of the MSP algorithm with real imagery data, at both image level and patch level. Throughout these experiments, rather than visualize all bases, routinely show the top bases learned-heuristinn the top bases are those with the largest coefficients (here, in terms of norm-.
Image Level. At the image level, first vectorize all 60,000 images in the MNIST dataset (Le- Cun et al., 1998) into a single matrix Y E 2278460.000 then create imperfect measurements based on models specified in Section 3: YN (MNIST with noise), Yo (MNIST with outliers). Yo (MNIST with sparse corruptions). We run the MSP algorithm with Y, YN, Yc, Yo and compare the learned bases. Figure 4(a), (c), (e), and (g) show examples of Y, Yx, Yo, and Yc, and Figure 4(b), (d), (f), and (h) show top 10 bases learned from Y, YN, Yc. Yo. respectively. Despite that we use different types of imperfect measurements of MNIST, the top bases learned from MSP algorithm 3 are very much the same. 10 This result corroborates our analysis: the &- maxxmizzaiinn and the MSP algorithm inherently insensitive to noise, robust outliers, and resilient sparse corruptions.
3
4
6
6
3 6
9
/
9
(a) Normalized MNIST to mean 0 and std
(b) Top bases from MNIST
3
5
8
2
4 4
9 9
0
/
3
I
(c) MNIST with noisc, SNR 3.333
(d) Top bases from MNIST with noise
?
6
g
/
(c) MNIST with 50% outliers
(f) Top bases from MNIST with outliers
6
4
0 q
3
8
g
3
7
(g) MNIST with 50% sparse corruptions
(h) Top bases from MNIST with sparse corruptions
Figure 4: Left: Examples MNIST and its different imperfect measurements. Right: Learned
bases from MNIST and its different imperfect measurements using the MSP algorithm 3. Patch Level. A classic application of dictionary learning involves learning sparse representations of image patches (Elad & Aharon, 2006; Mairal et al., 2007). In this section, extend the experi- ments of Zhai et al. (2019b) to learn patches from gray scale and color images. First, we construct a data matrix Y by vectorizing each 8 8 patch from the 512 x 512 gray scale image, "Barbara" (see Figure 5). We then run the MSP algorithm with 100 iterations on both and a noisy version YN, and the learned top bases visualized in Figure 5.
(a) Clean Image and Bases
(b) Noisy Image and Bases(SNR = 5.87)
Figure 5: The top 12 bases learned from 16 16 patches Barbara, both with (b) and without (a) noise. The noisy image is produced by adding Gaussian noise the clean image, resulting in signal-to-noiss ratio (SNR) of 5.87. We observed similar effect when using an 8 x patch size.
Analogously, we apply the same scheme to 256 256 color image, "Duck" (see Figure 6), convert- ing each 8 8 x patch into a column vector (in R 192) of Y. Notice this forces the algorithm to learn bases involving all three channels simultancously. rather than at time. After running the MSP algorithm for 100 iterations, we visualize the top bases learned from both Y and corresponding YN in Figure 6.
We next consider the problem learning a "global dictionary" (Mairal et al., 2007) for patches from many different images. To construct data matrix Y, randomly sample 100,000 8 8
Bases with opposite intensity are considered as the same base, since they only differ by a sign.

---

Published as a conference paper at ICLR 2020
(a) Clean Image and Bases
(b) Noisy Image and Bases (SNR 6.56)
Figure 6: The top 12 bases learned from all 8 x 8 x 3 color patches of the clean and noisy image, respectively. Here, the SNR of the noisy image is 6.56.
(a) Bases from Clcan Patches
(b) Bases from Noisy Patches (SNR -6.23)
Figure 7:
Top half (96) bases learned from 100, 000 random 8 x 8 x 3 patches sampled from CIFAR-10. 10, before and after adding Gaussian noise, with SNR 6.23.
patches from the CIFAR-10 data-set (Krizhevsky al., 2009). A noisy data matrix YN, is then generated by adding Gaussian noise. Again, we apply the MSP algorithm with 200 iterations to learn 192 bases and visualize the results in Figure 7. We leave the experiments of CIFAR-10 with outliers and sparse corruptions in the Appendix due to limited space.
In each of these experiments, the top bases the learned dictionary remain relatively unchanged with the addition of noise. To quantify this similarity, take the top bases from the noisy dictionary and find the closest top clean base for each. If the bases are nearly identical, then the inner product of each of these pairs should be close 1. Table reports the statistics.
Minimum Lower Quartile Median Upper Quartile Maximum
Barhara 0.3048
0.8471
0.9941
0.9993
1.0000
Duck 0,2510
0.9782
0.9891
0.9971
1.0000
CIFAR-10
0.5147
0.7203
0.9892
0.9998
1.0000
Table Statistics about the inner products between the top 20 noisy bases and their corresponding closest top-20 clean bases.
CONCLUSION AND DISCUSSIONS
In this paper, find the -ormo maximization based dictionary learning and corresponding MSP algorithm introduced by Zhai et al. (2019b) have strong geometric and statistical connections to classic data analysis methods PCA and ICA. These connections seem be the reason why they all admit similar simple and efficient algorithms. Empirically, we have observed that f'-norm maxi- mization is surprisingly insensitive noise, robust outliers, and resilient sparse corruptions. Moreover, such empirical observations corroborate our concentration analysis-larger data samples (p) improve the stability and robustness of the L mm-aimmizaaionn based dictionary learning.
From experiments on real images, we observed that top bases learned are rather stable but tail bases can be less stable (see Figure 10 in Appendix C). We conjecture this phenomenon happens due to the fact that real images generally do not follow the uniformly sparse Bernoulli Gaussian model (of equation 14). Generalizing dictionary learning to non-uniformly sparsely generated data would be good topic for future study. Finally, note that Bai et al. (2018) has established subgradient descent can find global optimal solutions for dictionary learning, an interesting theoretical guarantee since dictionary learning problems do not satisfy the standard structural (i.e. generalized convexity) assumptions that guarantee global convergence (Ben- Tal & Nemirovski, 2001; Zhou et al., 2017a; Nesterov, 2013; Zhou et al., 2017b 7b; Bubeck et al., 2015; Zhou et al., 2017c: 2018; Ma et al., 2018; Chi et al., 2019). It would be desirable, although highly challenging, to establish similar global convergence guarantees for MSP algorithm. We leave that for future work.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
P-A Absil and Jéröme Malick. Projection-like retractions matrix manifolds. SIAM Journal on Optimization. 22(1):135-158, 2012.
Andreas Argyriou, Theodoros Exgeniou, and Massimiliano Pontil. Convex multi-task feature learn- ing. Machine Learning, 73(3):243-272, 2008
Yu Bai, Qijia Jiang, and Ju Sun. Subgradient descent learns orthogonal dictionaries. arXiv preprint 1810. 2018.
Boaz Barak, Jonathan Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In STOC, 2015.
Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algo- rithms, and engineering applications, volume 2. Siam, 2001.
Wlodzimierz Bryc. The normal distribution: characterizations with applications, volume 100. Springer Science & Business Media, 2012.
Sébastien Bubeck al. Convex optimization: Algorithms and complexity. Foundations and Trends Machine Learning. 8(3-4):2313377 2015.
Meghan K Cain, Zhiyong Zhang, and Ke-Hai Yuan. Univariate and multivariate skewness and kurtosis for measuring nonnormality: Prevalence, influence and estimation. Behavior Research Methods, 19(5):771-11755 2017.
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):11, 2011.
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255- 308, 2009.
Niladri Chatterji and Peter L Bartlett Alternating minimization for dictionary learning with random initialization. In Advances in Neural Information Processing Systems, pp. 1997-2006, 2017.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factoriza- tion: An overview. IEEE Transactions on Signal Processing, 67(20):5239 5269,, 2019.
Lawrence T DeCarlo. On the meaning and use of kurtosis. Psychological methods, 2(3):292, 1997.
Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing, 15(12)33736 3745, 2006.
Dar Gilboa, Sam Buchanan, and John Wright. Efficient dictionary learning with gradient descent. arXiv preprint 1rXiv:1809.100 10313, 2018
Nathaniel E Helwig. Principal components analysis. 2017.
Peter Huber. Projection pursuit. The annals of Statistics, pp. 435 475, 1985.
Aapo Hyvärinen and Erkki Oja. A fast fixed-point algorithm for independent component analysis. Neural Computation, 9:1483-1499 1492, 1997.
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural networks, (3(4-5):41-4400 2000.
Aapo Hyvärinen, Jarmo Hurri, and Patrick O Hoyer. Natural image statistics: A probabilistic ap- proach to early computational vision., volume 39, Springer Science & Business Media, 2009,
Ian Jolliffe. Principal component analysis. Springer, 2011.
Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, (Feb):517-553, 2010.

---

Published as a conference paper at ICLR 2020
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Han-Wer Kuo, Yenson Lau, Yuqian Zhang, and John Wright. Geometry and symmetry in short- and-sparse deconvolution. arXiv preprint
2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):22782222333 2324,, 1998.
Ann B Lee, Kim Pedersen, and David Mumford. The nonlinear statistics of nigh-contrast patches in natural images. International Journal of Computer Vision, 54(1-3):83-103, 2003.
Yanjun Li and Yoram Bresler. Global geometry of multichannel sparse blind deconvolution on the sphere. In Advances in Neural Information Processing Systems, pp. 1132 1143, 2018.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statis- tical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, pp. 1-182, 2018.
Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of- squares. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 438 446. IEEE, 2016.
Julien Mairal, Michael Elad, and Guillermo Sapiro. Sparse representation for color image restora- tion. IEEE Transactions on image processing, 17(1):53-69, 2007.
Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro, and Andrew Zisserman. Diserimina- tive learned dictionaries for local image analysis. Technical report, MINNESOTA UNIV MIN- NEAPOLIS INST FOR MATHEMATICS AND ITS APPLICATIONS, 2008
Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. IEEE transactions on pattern analysis and machine intelligence, 34(4),791-804, 2012.
Julien Mairal, Francis Bach, and Jean Ponce. Sparse modeling for image and vision processing. Foundations and Trends in Computer Graphics and Vision, (12-3):5--283, 2014. ISSN 1572- 2740. doi: 1006000000000000088.
Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaël Varoquaux. Dictionary learning for mas- sive matrix factorization. In International Conference on Machine Learning, pp. 1737-1746, 2016.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Thanh Nguyen, Akshay Soni, and Chinmay Hegde. On learning sparsely used dictionaries from incomplete samples. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3769-3778, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Bruno A. Olshausen and David J. Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature, (6583))60776600 1996.
Bruno A. Olshausen and David J. Field. Sparse coding with an overcomplete basis set: A strategy employed by VI? Vision research, 37(23):3311-322 1997.
Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang, and Zhihui Zhu. Analysis of the optimization landscapes for overcomplete representation learning. arXiv preprint
2019.
Sirisha Rambhatla, Xingguo Li, and Jarvis Haupt. Noodl: Provable online dictionary learning and sparse coding. International Conference on Learning Representations, 2019.
Mare' Aurelio Ranzato, Y-Lan Boureau, and Yann LeCun. Sparse feature learning for deep belief networks. In Advances in Neural Information Processing Systems (NIPS 2007), volume 20, 2007.
12

---

Published as a conference paper at ICLR 2020
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501. 2010.
Tselil Schramm and David Steurer. Fast and robust tensor decomposition with applications to dic- tionary learning. arXiv preprint arXiv: 170.00777 2017.
Daniel A Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pp. 37-1, 2012.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery the sphere. arXiv preprint arXiv:1504.06755 2015.
Martin Wainwright. High-dimensional statistics: A non-asymptolic viewpoint, volume 48. Cam bridge University Press, 2019.
John Wright, Allen Y Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Robust face recognition via sparse representation. IEEE transactions on pattern analysis and machine intelligence, 31(2): 210-227, 2008.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust PCA via outlier pursuit. In Advances in Neural Information Processing Systems, pp. 2496-2504, 2010.
Huan Xu, Constantine Caramanis, and Shie Mannor. Outlier-robust PCA: The high-dimensional
case. IEEE transactions on information theory, 59(1):546-572, 2012.
Jianchao Yang, John Wright, Thomas S Huang, and Yi Ma. Image super-resolution via sparse representation. IEEE transactions on image processing, 19(11):2611-287) 2010.
Yuexiang Zhai, Zitong Yang, Zhenyu Liao, John Wright, and Yi Ma. A fast holistic algorithm for complete dictionary learning via e norm maximization. Signal Processing with Adaptive Sparse Structured Representations (SPARS), 2019a.
Yuexiang Zhai, Zitong Yang. Zhenyu Liao, John Wright, and Yi Ma. Complete dictionary learning via - maximization over the orthogonal group. arXiv preprint arXiv: 19iv:1906.02235, 2019b.
Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, and Yi Ma. Simultaneous rectification and alignment via robust recovery of low-rank tensors. In Advances in Neural Information Processing Systems, pp. 1637-1645, 2013.
Xiaoqin Zhang, Zhengyuan Zhou, Di Wang, and Yi Ma. Hybrid singular value thresholding for tensor completion. In Twenty-Eighth AAAI Conference Artificial Intelligence, 2014.
Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, and Yi Ma. Robust low-rank tensor recovery with rectification and alignment. IEEE transactions on pattern analysis and machine intelligence, 2019.
Yuqian Zhang, Han-War Kuo, and John Wright. Structured local optima in sparse blind deconvolu- tion. arXiv preprint arXiv:/806.00 0806.0038, 2018
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter Glynn. On the convergence of mirror descent beyond stochastic convex programming. arXiv preprint 1706. 2017a.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent in variationally coherent optimization problems. In Advances in Neural Information Processing Systems. pp. 7040-7049, 2017b.
Zhengyuan Zhou, Panayotis Mertikopoulos, Aris L Moustakas, Nicholas Bambos, and Peter Glynn. Mirror descent learning in continuous games. In 2017 IEEE 56th Annual Conference Decision and Control (CDC), pp. 5776-5783. IEBE, 2017c
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W Glynn, Yinyu Ye, Li-Jia Li, and Fei-Fei Li. Distributed asynchronous optimization with unbounded delays: How slow can you go? 2018.
13

---

Published as a conference paper at ICLR 2020
A PROOF OF SECTION 3
A.1 PROOF OF PROPOSITION 3.1
Claim A.1 (Expectation of Objective with Small Noise) 40 (0, 1). let X. E RRxx, Fi,5 Wid BG( Let Do O(; IR) be orthogonal matrix and assume Y = DoXo For any orthogonal matrix W E (m;; IR.) and any random Gaussian matrix G E guxp, 9i. rid N0, If) independent of X let YN = Y + G denote the data with noise. Then the expectation of mp I YN Il satisfies:
W Doll
E Ex.. G [ Yv 30(1 -0) np
30 601) + +3
(23)
n
Proof Let W' M (n;; R), notice that the orthogonal transformation (W G) of Gaus- sian matrix (G) is still a Gaussian matrix and satisfies (W*G)., ~ (0, 1), and it is independent of (X.). We abuse the notation a bit let G W in the following calculation, since W G is also a Gaussian matrix independent of X. and it will not affect the final result.
Ex.,G | YN
Ex..G |MX, + G
Bx..c
Σ
miKKki + 9i.j
27
n G
a
Σ
mi,k 2k.
+ 6E G
n Σ
mi &.k
Eogis
n
2
(24)
Ex..G
mi,
+ Exx
Mi, M.k
3repm
Ex, G
Σ
m Tkj
+ 6mpbr7² 5mpp072+3npmm +3mpm*
Ex | o1 + 6mp0r) + 3mpp
=3p0(1 8) |M + 3npd2 + 6пpbn + 3mpm"*
therefore,
1 Ex.. G IWWY' 30(1 - 0) W Doll
30 + 60m² +n
(25)
np
n
which completes the proof.
A.2 PROOF OF THEOREM 3.2
Claim A.2 (Concentration of Objective with Small Noise) 0O E (0, 1). let Xo E Raxp, Fig rid (O). Let D. E O(n; R) be an orthogonal matrix and assume DoX.- For any orthogonal matrix W E O(n; R) and any random Gaussian matrix G Raxp Nexp,,i.. .9i.j Mii (0, independent of X., let YN = Y + G denote the input with noise, then:
P sup
1
W BESE-EWWWEE
Y 11
2 <
1
(26)
W (e)();)) np
p
when p Ω ((1 + ) n Inn/
Proof According Proposition 3.1, we know that
1 E Ex..G W Yv 30(1 0)
W D.ll.
+02 + 60mr + +3
(27)
np
14

---

Published as a conference paper at ICLR 2020
Moreover, since Yv (// + 91. + 92. ....... Up 9pl. whose columns are independent. Let
Z = [2 Z2g ... 2pl D [x] + 91, 22 + 92.............................. Ip + gpl = X, G
(28)
note that abuse the notation bit by assuming D G, since D is also Gaussian matrix independent of X, and it will not affect the final result. Define function (=(W) (ne R) - R as
f=(W)
||
(29)
Next, we will check assumption 1, and 3 then apply Lemma B.4.
Assumption 1: pln, p). Since 25.5 = Pi. we know that with probability 0, 2 ~ (+,,)++))))
and with probability - 0, z N (0, 1). Hence,
B²
Ba
P max Linl > B) - 2np0 exp
+ 2np(1 -0) exp
= u(n.p).
(30)
2 2112
2
Specifically, we set B = In p. which yields
(m
(In
u(n,p) p) 2mp0 exp (
2mp(1 exp
(31)
2 + 2n/2
Assumption 2: Lipschitz Constant Ly. By Proposition 3.1, VW E O(;; R), we know that
(W2 30(1 - 0) [[W-Doli 3nd2 + Gn0n + 3nny".
(32)
Hence, 1W1, W2 (nn; IR), we have
E [ = 38(1 - 0) W WiiD.1l. W =||1
I W:
(33)
moreover,
DWi -W;
([WW) - (.D..) [WT + (W; ".).g)
1/2
1/2
(34)
[W" Do) - D.)
(WT 12 + +W, Do)
i
(W D2) - DW 02 (W D.)
(Wi) (o) 121
< W. W Dol1z WiD. W Doll (I D.l12 + W D.l12)
<4n² W D.- -W; Do12 4n2 W W2ll2-
Hence, we know that
E B| - [W =11 < 12n²0(1 - 0),
(35)
which yields
L = 12 -)).
(36)
Assumption 2: Lipschitz Constant T.y. Since f=(W) = W E|| [W* we have
W W | =|||
[[WTT)) (W 2) [W] + (W)
1/2
1/2
(Wi (W (W)=)}1²²
(Wiz)² + (W;=)?1²
(37)
(Wiz)02 11 (W 02 + (W₂ 2)
15

---

Published as a conference paper at ICLR 2020
For 11, we have
T T= - (W; - o (Wi 2) + 22
$ W1 WVi-W11: Wi
Wallg
E212 - 2n.B² W W2
(38)
22
EnB
For 22 have
12 - [|]]) + (Wiz) S (W + (W
(39)
< [ + W3 2nB²²
Hence, we know that
| 1W 1 4n² W1 W2lp:
(40)
which yields
L, = 4n²
(41)
Assumption 3: Upper Bound R1.
Notice that AW Onn;R),
W
fz(W) = W -1 [
S
W 211; = =1=11 - n² = RR
(42)
W
Assumption 3: Upper Bound Rz. Vi [n].
Assume the support for æ is S, so we know that know that
if S, otherwise,
24
(43)
U1:
where v NNO,, I) is Gaussian vector. Let Ps
R
+ R" be projection that satisfies Vig E IR
V1
i otherwise.
(Ps9),
(44)
q::
Moreover, vW E (m; RR), let wy denote the 7th column vector of W. hence
(( = E [IW"
Wis 2) (m0j. 2)
1=1
(45)
E (Psw,, 4)a (Psw 03*| < EE
(Psw,, w\a² E (Psw,, (Psw,,))8
<Es
Notice that v ~ NN. therefore Vi E [n], we have
E (Psw;, w)a = 105 Ps
(46)
hence
n
(Psw; w)8² E (Psw;, 0/ 105IS
Es
Psw; PPswil
j=1
=105
Σ> Σ
Es
(1 + " kES) w
(47)
i=1 j=1
Ag.
72
<105(1 + 2)
[WZ 2 w N 105(1 + 172
j=1 ks A Ris Aoa
Therefore, we can conclude that
T9 [ 5 105(1 + 2 = R2.
(48)
16

---

Published as a conference paper at ICLR 2020
Applying Lemma B.4 for Concentration.
Now apply Lemma B.4 with
1.
= lnp, p(n,p) = 2mp2 exp (- [((np) + 2mp(1 - 0) exp
(- (1n
(49)
4
2
2.
T = 11 - -0), T,p= = 4n² (n2
(50)
3.
Ri (Inp)) R₂ 105(1 +1 n
(51)
we have
1
P
sup
Σ fx, (W) Bf2 (W)] 26
(e0()) Tpp
1
=P
sup
I 11
SiIW-YNIl 111 2
ni
pn²02
1 + Ls)
(52)
< exp
+ n2 In
In2
+ u(n,p)
32R2 + no
nd
3p8²
+ + (60m(Inp)
<exp
+ 1n 2
C(1 + 17221 + ())
(Iup)2
(In p)
< 1
+ +2mp0 exp
+ 2mp(1 - 0) exp
-
4
for constant C > 104 when p 2 ((1 n²))4n²2mm/68))
A.3 PROOF OF PROPOSITION 3.3
Claim A.3 (Expectation of Objective with Outliers) AA E (0, let X E Raxp, Ii,s Rid
BG( Let Do O(;; R) be orthogonal matrix and assume Y = DoXo- For any orthog- onal matrix W E O(n; R) and any random Gaussian matrix G' E 1P Kog mid (O, 1)
independent of X., let Yo = [Y denote the data with outliers G'. Then the expectation of
1. || Yo Yoll; satisfies:
mp
Yo =30(1-1--1000 0) W D. + +30 33.
E x Ex G
(53)
np
n
Proof Notice that
EX..G' W Ex. | Bo |
(54)
and
Ex. W W W'D.x..11 3p - 0) W + 3npo
(55)
Moreover, the orthogonal rotation (W G') of a standard Gaussian matrix G' is also a standard Gaussian matrix, therefore,
Eg [ G 3rnp.
(56)
Hence,
1
x & I 30(1 0) | D. 11 + +02 +3T,
(57)
np
n
which completes the proof.
17

---

Published as a conference paper at ICLR 2020
A.4 PROOF OF THEOREM 3.4
Claim A.4 (Concentration of Objective with Outliers) 40 E (0, let Xo E RRxxp, Figj wiid BG(O). Lel D O(;; IR) be orthogonal matrix and assume Y DrX For any orthogonal matrix W E (m; IR) and any random Gaussian matrix G' E RuxTp, Rig med N(0, 1) indepen- dent of Xo. let Yo |Y, G') denote the input with outlier G¹, then:
P sup
W - W 26 < p
(58)
(eo(n:R)
Top
when p n2 In n/2).
Proof Notice that
P sup
Yoll W
Yoll 20
WE)(nRR) np
P
sup
[ Y 1 E
1
IV
WcO(n: np
(59)
P
sup W ())():)) Ti
G -
Apply Lemma B.5 (substitute d with 9) I,, know that
| E |' 2 5
r =P
sup WeO(m;) np
3p5²
120mp(In
< exp
+ n In
(60)
c10 + 16n((1
po²
120mp(Inp)*
(In p)
+ exp
+ n² In
+ 2mp0 exp
c2
2
2p
for two constants ei 2 4 x 10 > 13, 440, and the last inequality holds when
9(On² n/ Moreover, apply Lemma B.5 again (let 0 1, G' Raar and substi- tute 8 with 2-), ), we have
P2 =P
sup W ()) np
W
2
sup WEO(m:) Tup
W -WIG
IV
2T
(61)
3p(0/7)²
120mp(Inp)²
< exp
+ n²
Ci + 16n(Inp)46/7
8/7
p(5/T)2
n² In 120mmp(mp))
(In p)
1
+ exp
+ 2mp exp
C2
8/T
2p"
for two constants Ci
2
4 x 10 C2 > 13, 440, and the last inequality holds when
=
2(7 n//))). Combine < and can be larger than 1, we conclude that
1 W - E Bl Yoll 26
1 (62)
P sup WeO(n:) np
<Ti+T2
<
P
when p = 92 n Inn/8))
18

---

Published as a conference paper at ICLR 2020
A.5 PROOF OF PROPOSITION 3.5
Claim A.S (Expectation of Objective with Sparse Corruptions) 40 E (0,1), let X. E Ruxp, Fii mid BG( Let D, E ( R) be orthogonal mairix and assume Y DoXor For any orthogonal matrix W E (n; R) and any random Bernoulli matrix B E R bug Wid Ber(3) independent of x let Yc Y + BBo denote the data with sparse corruptions, and S E gaxp
defined in equation 15. Then the expectation of I [W-Yll's satisfies:
|
D. 12
11 + +30 6o2 + 30
E x B.S WW = 30(1 0) np
o -(1
n
(63)
Proof Let W* = M E (n; RR, notice that
[
(64)
hence
B, | Yoll. = Es
mi. +
Wk, x bb. Sk.5 skk
tml
k=1
B x. B,
Σ
+6
my &.I.d
Wk j Skot
1=
P1
12
(65)
0
Wk, bk.
+4
Σ
Wk, be. Sk.
k=1
R
T's
14
3
+ 4
mi.
wK
1=1
Moreover,
Ti:
n Ex.. I1 =38 Σ
m + 602
Σ
m m
k=1
ckann
(66)
n1
=30(1 - 8) Σ
mi + 302
A=1
Dg :
2
27
n
B.s.
Ex,
Σ
mi,KDKk.
E
wk, wh.
(67)
12
2²3
Σ
wh.i = 0²03,
mi,k
km
P3 :
a
Ex.. -EB,ST' 043 Σ
Wk + 664
Σ
wh u Ezg
k=1
Iskickosn
(68)
n
-0A3(1 1 3,9) Σ
k + 30 304
km1
19

---

Published as a conference paper at ICLR 2020
Ts
B.s =
B.s, 0.
(69)
Substitute ET', ET' 2, BT's, ET1s ET's back equation 65, yields
1
W' Dolli 0 1113(1133))
[ + 300 +60-03+30 (70)
Ex B,9 WY 30(1-0)
np
n
n
A.6 PROOF OF THEBREM 3.6
Claim A.6 (Concentration of Objective with Sparse Corruptions) 40 E (0. 1), let X. E Ruxp, Vi,j mid (G( Let D, E (nn; R) an orthogonal matrix and assume D.X For any orthogonal matrix W E On; R) and any random Bernoulli matrix B R b.j Rid Ber(B) independent of X let Yc Y + a oB denote the inpus with sparse corruptions, and S E Rnxp is defined in equation 15, then:
1 - Yoll" 2 )
P sup WEO(m:))
<
(71)
mp
when p = Q 3n lnn/8))
Proof According Proposition 3.5, know that
W Yell 30(1 0) W D. l
W
Ex B.S npp
+ o
801 -33)
+ 30 + +60203 + 400
(72)
Moreover, since Yc = yy + ob y2 + ob .2,..... yp + ob, spl. whose columns are independent. Let
Z 21, 22..... zpl D.Yo X, oC,
(73)
where C-
D S).
Note that the columns of are independent, we can define function
f=(W): Onn R)
+ R as
(wW)
| ||
2||
(74)
Next, we will check assumption 1, 2, and 3 then apply Lemma B.4.
Assumption 1: (:(nnp)). Since Z = X. + oC, we have
(max 1g
| > B} = (max [.i + oeas > B) C {max 1.
[aas > B a max
(75)
i.
Moreover, since
max leis S max ||d:l1 S Vn. (
(76)
have
(max hg
|zsi B}
{max Fi,ن B B-owl ovn.. bg
(77)
Thus know that
(B- (iB-oVT)) -0-ov
P
max Ea. >
B
<
max |ii > B ov7)
< 2mp0
(78)
2
Specifically, we set = pd, which yields
(pà (pi-ovi))
p(n, p) = 2npo exp
(79)
2
20

---

Published as a conference paper at ICLR 2020
Assumption 2: Lipschitz Constant Ly.
By Proposition 3.5, vA Onx; R), know that
f (W) 30(1 - 0) || W D. Doll 0² 33) W W|] + 3nd + 65 + 3no B². (80)
Hence VW1, W2 E (n;; RR, we have
E W E W
(81)
<30 W.D. [ D. +0+3(1 -33) | 11 [
from the derivation of equation 34, we have
|| D. [Wi s 4n² [W1 W2ll2
(82)
and therefore, we have
Wi=lll E w < [12n20 - 0) 131
- -33]
W W2ll
(83)
which yields
f = 12n20(1 B) + 4n 3(1 33).
(84)
Assumption 2: Lipschitz Constant Ly. equation 37, we have
Since fs (W) W 2|| apply the same derivation as
WF IW5 - B W W2l2
(85)
which yields
L, = 2 B*.
(86)
Assumption 3: Upper Bound Ri.
Notice that vW E O(;; RR),
W
fz(W) = W 2 W
2
21 = =1 S B R1. W
(87)
Assumption 3: Upper Bound Rg. Assume the support for æ is S, so we know that Vi E [n]].
1t + Ci, i S, otherwise,
(88)
C₁.
where v (0, is a Gaussian vector and c =
(b 8) is the sparse corruption vector after orthogonal rotation D Let Ps R - IR" be a projection onto the support S, that is, Vq E R
(Psq): = gi 0.
if E otherwise.
(89)
Let M D.W, W. and bo s, we have
E E W) =E (IIW*2 =115
E
((w) .)) + (m, h2))* ((w5 æ) + (mn)h)))
(90)
E (ww, x)) + (m,,)) (ww, x) + (m, 12:)8]
((Psw; v) + h)) E E(Pssw, v) (m,, 12)) 11))88
21

---

Published as a conference paper at ICLR 2020
Moreover, have:
E (Psws u) + (m; h))*
= (Pswi, 0))) + 2802E (Pswws, w/ (mi; 11)2)) + 70o'B (Psw:; 0)² (mi, hi)")
(91)
+ 28 (Psws,, w/ (m, h))²) + oOE (m, 11)²)
We now provide upper bound for E ((Psw; w)") and E ((mi, h)") for r = 2,4,6, respectively. Since Eh - 0 and h bo Let S" denote the support of h, we have
E (m,, 11))
E II
Σ
manctt
1=1 -1==
(92)
Es f - kos man (Rees))
Now we discuss these cases separately:
With probability (c S 1), all k1, 12, k3, ky are in S. in this case, have
Σ Es : d (RGES))
(93)
mi =
With probability 02 I 1), only three among ki, h2, ka, ka are in S' in this case, we have
Σ
Es (mi Ik I Ahess
(94)
Σ
(mb m m mba.)) = = S.
Ag
With probability cg I 1), only two among hi, k2 ks, Ka are in S', in this case, we have
Σ
Es knsssmm 1 lsses lkgesmm 1 Jsess)
(95)
Σ
(mi,
+
Σ 11,
(m2 S [|m + |mmill 2.
With probability cag(cs < 1), only one among ki, k2 ha, ha is in S' in this case, we have
Σ Es i lkees ileess (REE)))
l ks
(96)
Σ
m
-|mm 1.
Hence, combine equation 93, equation 94, equation 95, and equation 96, know that
E (m, h) cg, for constant 1. Similarly, one can conclude that
(97)
E ((m,, h))) & cB, Moreover, since v NNO,,) I). we know that
Vr = 2,4,
(98)
E ((Psw; w)") P
Vr 2,4,6,8.
(99)
22

---

Published as a conference paper at ICLR 2020
Hence, with the similar technique applied above, we have
E (Pswi, )) 105E |
(100)
=105
Σ
Es (w Lu A Jeges i (RLES)) S 105c0,
k kk.
for constant 1. Similarly, we have
E ((Psu; u)") = || 112 S c(r - 1)!! Vr = 2, 6,
(101)
for a constant c > 1. Therefore, combine equation 91, we have
E ((Psu; v) + (m;, h))
=B (Psw;, w)*)
28 (Pssws, w) (m, h1²²) + 70 (Pssw,,)) w)* (i)
(102)
+ 28 (Psw,, w) (m, h))) + O (m,, h1)²) <.0 2 203 + 003 28co 03 + co S ca B,
for constant 1. Hence, combine equation 90, we have
= E =10"=
ΣΣΣ j=
E ((Psw; u) + a (m; h))² ((Pswy, f) + a (m,, h))88 h)) S co Bn?
(103)
for constant
1. Therefore, we can conclude that R₂ = co Bnn
(104)
for a constant >
Applying Lemma B.4 for Concentration.
Now we apply Lemma B.4 with
1.
(p'-ovin ooo
B B=pt. pt, p(n.p) 2mpp exp
(105)
2.
L, = 12m20(1 - 0) + 4 03 -(1-33))
L, = 4n²p.
(106)
3.
R1 = n2pp
Rs co Bn²
(107)
for a constant c >> 1, we have
P
sup
Σ [2, (W) Bf2, (w)l 26
(eO(nR) Ti
1
=P
sup
1 E WlI Ycll 2
(n)
Tip
222
12(L, + [,)
<exp
+ + In
In 2
+ p(n.p)
(108)
32R₂
8R/nó/3
nd
3po²
60np
<xxp
+ n In
In
Co + Snpo
pp
-o/n
1
2np0 exp
p
for a constant C 96, when p = 12 (2 3n² l
23

---

Published as a conference paper at ICLR 2020
B RELATED LEMMAS AND INEQUALITIES
Lemma B.1 (Two-sided Bernstein's Inequality) Given random variables 21, 22, Fp if E
[p] ail S b almost surely, then
pt
IP
x
E[ri]] 21
2exp
(109)
P
2
D B + +b2bt
/3
Proof See Proposition 2.14 in Wainwright (2019), one easily generalize it two-sided case.
Lemma B.2 (Entry-wise Truncation of Bernoulli Gaussian Matrix) Let X E RRXP, where Fif rid (G) and let Il denote the maximum element (in absolute value) of a matrix, then
12
PP max pris 21) < 2mp0 exp f.
(110)
2
Proof A Bernoulli Gaussian variable Tz, Vi E [n].j E [p] satisfies Dif bag aid Ber(f), 96, wad NO, 1) and therefore
b gi,j where
t²
P P([zp) 2) 0 IP (l 2 2t) s 20 exp
(111)
2
By union bound, we have:
(_
f2
P max Fayl 22
P( [ri 2) I 2mpt exp
(112)
1.
Lemma B.3 (c-Net Covering of Stiefel Manifolds) 1 There is a covering c-net Se for Stiefel manifold M (W Raxr W-W [,,(n 2 r) operator norm
vW E, WE E Se subject to
IW
W S.
(113)
of size |S.] & (6) "r
Proof See Lemma D.4 in Zhai et al. (2019b).
Lemma B.4 (Uniform Concentration bound over O(n; Let E RRx be a random matrix whose columns 21, 22....;
: 2p are i.i.d. drawn from distribution P. Vz P, let fz(-) 0(n; R) R. denote function that maps ( R) to R. vB O. let Z denote the truncation of Z:
Zi.jj
if |2, B,
S.
Σ,,
0
otherwise.
(114)
Assume that:
IP (max.,j |ata]
B) < p(n, p), where p(n.p) O as p increase, depends on p.
2. (.) is Lipsschit and fz(-) is L Lipsschit that is. VW1, W2 E O(n:R),
(W1 (W S Ly W W2l12
(115)
(fe(W) fa (W2) < L, [ W2l1
3. AW E (n;;R) IR), f=(W) < R1. B[ < R
A similar result be found in Lemma 4.5 of Recht al. (2010).
24

---

Published as a conference paper at ICLR 2020
Then:
P
sup
(W) - Bs2, (w))
20
(eO(n:R)
np
i=1
(116)
pn pn²8²
1 + =b1)
< exp
+ n In
+ 1n2
+ p),,p),
32R2 + 8R1n8/3
nd
when p > p. where depends
Proof By assumption 1, we have
P
sup WcO(n:R np
Σ
[s (W) Efz, (W))
j=1
<P(Z + 2) +P
sup (e)(
Σ f2 (W) (w) - BF)
2 nd
(117)
j=1
Su(n,p) p) +P
sup WeO(m:3)
Σ (w) - (W)
2 28
Uniform bound over O R). (n; R):
Ve 0, lemma B.3 shows there exists an e-nets S, that covers
[S_
S. (11, W2, Wis O(n; Rm; C
U B(W,
(118)
1=1
and [S.] satisfies |S.| < (6/e)=². Together with Lipschitz assumption 2, we know that
2 Se, (W) - (W)
sup WeB(W..c)
1=1
P
sup WEB(W..e)
Σ (Wi) (Wi)
sup WEB(Wi.e)
(W)) Efz(W)
1=1
(119)
fz, (Wi) - P - fe, (w)
sup WEB(W.e)
P }=1
Σ fz, (Wi) (fi
(L, L,)e.
sup W.))
p
Hence, let
ng 2(L L
(120)
25

---

Published as a conference paper at ICLR 2020
have
P Jey (W) (W)
P
sup
2 nd8
2nd
(EO(n:3))
j=l
|S.|
P
Σ fz, (W) BW)(WW) nd
sup (EB(W
(121)
6 n²
P
sup WEB(W
f2 (Wi) Bsz(WW)
2 no 106--(e-- (1yle
P 9=11
1 + T11)
P
nd
exp
n²
In
P
sup WeB(Wod)
Σ P
fz (Wi) (f)
nd
2
Tail bound within each (WW,, c). Then, 4/ E [S.], we apply point-wise control given point W, E S. Later we will provide a uniform concentration bound over (n: IR). By triangle inequality, have
fzy Wi Efz, (Wi)
f (W)) Efz(WW)
+ Efz, (Wi) (fi)
P 3=1
(122)
VW E B(W,,& c), by assumption 1 and 3, we have
B& (W) Ef2, (W) = | [s)(W) 1242 S E2 f= |
(123)
E2 (W) |nn
B) I v R2p((n.))
Let be the lower bound of such that vp p. we have RRu(nn,)) nă we have
T Hence, when p.
+ nd 4
Σ fz, (Wi)
E5 (Wi)
S
Σ
fz Wii) Efa,
(124)
p
==1
which implies
nd 2
Sz, (W) Efz(W) > nō
P
- -W)
< P
p
4
1=1
(125)
22282
< 2
32R₂ + 8R,n8/3
where the last inequality is achieved by Bernstein's 's inequality (Lemma B. along with assumption and [ < (W) < R². Combine equation 125 and equation 121, we have
sup (e)(m;))
12 (W) Eʃ2 W)) 2 no
1=1
12( T.,)) nd
fz, (Wi) - Efz(Wi) 2 nd
(126)
< exp
n² ln
sup
WeB(Wrre)
2
j=1
222
12(L, + Lr)
<exp
+ n² In
+ In2
32R, + 88,35/3
nd
26

---

Published as a conference paper at ICLR 2020
Summary.
Therefore, we conclude that
P
sup (m) Tep
Sx, (W) - Efz (W))
20
(127)
pn2
[2(LL + +11
< exp
+ + In
+ ln2 + u(n.p),
32R2 + 8R
n2
when p > p.
Lemma B.5 (Concentration Bound of the Clean Objective over (nn; 4o (0,1), if X Rnxp, Fiij misd (G) for any ô > 0, the following inequality holds
P
sup
WX 1
E
28
WEO(n:R) np
3p8²
60mp(Iup))
< exp
n In
(128)
c10 + (m((n
p6²
60mp((mp)))
(In p)²
+ exp
+ n² ln
+ 2np0 exp
c20
2
for some constants > 104, C2 3360. Moreover
3p62
(0mmp((p))))
cxp
+ n²
c + 8n(Inp)
(129)
(_682 p8²
60mp(Inp) p)
1
+ exp
c0 + n² In
2np0 exp
8
2
when p = ((n In n/62).
Proof See Lemma 2.2 Zhai et al. (2019b), note that the sparsity condition 0 (0, of the original Lemma in Zhai et al. (2019b) can be easily generalized to 0 = 1.
C ADDITIONAL EXPERIMENTAL RESULTS
(c)
Figure 8: Representations of three 16 x 16 patches in both the clean and noisy images. Each selected patch is visualized, both with and without noise, and the corresponding bases with largest absolute coefficients are shown.
27

---

Published as a conference paper at ICLR 2020
(b)
Representations of three 8 3 colored patches in both the clean and noisy images. Each selected patch is visualized, both with and without noise, and the 6 corresponding bases with largest absolute coefficients shown.
Figure 9:
(a) Clean Patches
(b) Patches with Noise (SNR 6.23)
(c) Patches with Outliers
(d) Patches with Sparse Corruptions
Figure 10: All x 8 = 192 bases learned from 100, 000 random x 8 colored patches sampled from the CIFAR-10 data-set. (a) Learned Bases from clean CIFAR-10: (b) Learned Bases from CIFAR-IO with Gaussian noise, SNR = 6.23: (c) Learned Bases from CIFAR-10 with 20% of Gaussian outliers; (d) Learned Bases from CIFAR-10 with 50% of sparse corruptions. For all learned bases, the resulting atoms are sorted according to the ll-norm of their coefficients in the sparse code.
28


Reviews:
[{"review_id": "H1gO_IImcB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents results on Dictionary Learning through l4 maximization. The authors base this paper heavily off of the formulation and algorithm in Zhai et. al. (2019) \"Complete dictionary learning via l4-norm maximization over the orthogonal group\". The paper draws connections between complete dictionary learning, PCA, and ICA by pointing out similarities between the objectives functions that are optimized as well as the algorithms used. The paper further presents results on dictionary learning in the presence of different types of noise (AWGN, sparse corruptions, outliers) and show that the l4 objective is robust to different types of noise. Finally the authors apply different types of noise to synthetic and real images and show that the dictionaries that they learn are robust to the noise applied.\n\nOverall this paper makes significant contributions by extending the work in the paper referenced above to noisy dictionary learning settings and I would vote to accept based on these results.\n\nThe connections between Complete Dictionary Learning, PCA and ICA are interesting, but the algorithmic analogies seem superficial in my opinion. There are a lot of algorithms which follow a projected/proximal gradient descent scheme. If there are any deeper connections between the specific algorithms discussed, they should be spelled out more clearly. One point of clarification that I would like to raise is the similarity between the kurtosis and l4 objectives. This paper could be strengthened by delineating the conditions under which one would learn an ICA basis vs a Complete Dictionary. It seems to me that the only difference is in the generative model, and that maximizing the same objective under different data conditions could return an ICA basis or a Complete Dictionary. \n\nThe robustness theory and experiments on synthetic data are reasonable and demonstrate that complete dictionary learning is robust to the different noise conditions. I would like to how this technique compares to other complete dictionary learning algorithms (ER-SpUD, Complete dictionary learning over the sphere - Sun, Qu, Wright 2015) and whether the l4 objective is unique in providing this robustness. Another central claim of Zhai et. al. 2019 seems to be that l4 maximization is able to recover the entire dictionary at once, vs other algorithms that recover the dictionary one column at a time. To test this, I would like to see runtime evaluations and comparisons to other algorithms. While the claim of recovering the entire dictionary is true, it seems to me that requiring an SVD at each iteration would be very expensive. I am not completely convinced that the approach of estimating the entire dictionary would indeed be faster.\n\nTo summarize, I believe this paper would be a good addition to the literature on l4 maximization algorithms for dictionary learning. I am willing to adjust my score based on responses to the above concerns.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1x_np7Ctr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper explores the recently proposed $\\ell^4$-norm maximization approach for solving the sparse dictionary learning (SDL) problem. Unlike other previously proposed methods that recover the dictionary one row/column at a time, for an orthonormal dictionary, the $\\ell^4$-norm maximization approach is known to recover the entire dictionary once for all. \n\nThis paper shows that $\\ell^4$-norm maximization has close connections with the PCA and ICA problem. Furthermore, focusing on the MSP algorithm for solving the  $\\ell^4$-norm maximization formulation, the paper highlights the connections of this fixed-point style algorithm with such algorithms for PCA and ICA. Subsequently, the paper studies the behavior of the MSP algorithm in the presence of noise, outliers, and sparse corruption. Unlike PCA, surprisingly, the MSP algorithm is shown to be robust to outliers and sparse corruption.\n\nOverall, the paper makes a nice effort towards better understanding the relatively new $\\ell^4$-norm maximization approach and its connection with other well-understood problems in the literature. Moreover, the paper takes the right step by studying the effect of non-ideal signal measurements on the underlying goal of dictionary learning. That said, the reviewer feels that, in the current form, the results in the paper are not novel enough to warrant an acceptance to ICLR. The connection of the $\\ell^4$-norm maximization formulation with ICA have been previously noted in other paper, so this would hardly qualify as a novel contribution. The analysis of the MSP algorithm in the presence of noise, outlier, and sparse corruption is not comprehensive enough. It would have been nice if the authors had provided a non-asymptotic analysis of the MSP algorithm in the presence of non-ideal measurements. Also, it is not clear how interesting the outlier formulation presented in the paper is. Shouldn't one consider outliers that go beyond the Gaussian distribution, ideally arbitrary outliers?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main content:

Blind review #3 summarizes it well:

This paper presents results on Dictionary Learning through l4 maximization. The authors base this paper heavily off of the formulation and algorithm in Zhai et. al. (2019) "Complete dictionary learning via l4-norm maximization over the orthogonal group". The paper draws connections between complete dictionary learning, PCA, and ICA by pointing out similarities between the objectives functions that are optimized as well as the algorithms used. The paper further presents results on dictionary learning in the presence of different types of noise (AWGN, sparse corruptions, outliers) and show that the l4 objective is robust to different types of noise. Finally the authors apply different types of noise to synthetic and real images and show that the dictionaries that they learn are robust to the noise applied.

--

Discussion:

Reviews agree about the interesting work, including the connections of complete dictionary learning with classic PCA and ICA (after further clarification during the rebuttal period). Additional empirical strengthening during the rebuttal period also addressed a reviewer concern.

--

Recommendation and justification:

As review #3 wrote, "Overall this paper makes significant contributions by extending the work in [Zhai et. al's (2019) "Complete dictionary learning via l4-norm maximization over the orthogonal group"] to noisy dictionary learning settings".
Decision: Accept (Poster)