Title: GEOMETRIC ANALYSIS OF NONCONVEX OPTIMIZA-TION LANDSCAPES FOR OVERCOMPLETE LEARNING

Abstract: Learning overcomplete representations finds many applications in machine learning and data analytics. In the past decade, despite the empirical success of heuristic methods, theoretical understandings and explanations of these algorithms are still far from satisfactory. In this work, we provide new theoretical insights for several important representation learning problems: learning (i) sparsely used overcomplete dictionaries and (ii) convolutional dictionaries. We formulate these problems as 4 -norm optimization problems over the sphere, and study the geometric properties of their nonconvex optimization landscapes. For both problems, we show the nonconvex objectives have benign (global) geometric structures, which enable development of efficient optimization methods finding the target solutions. Finally, our theoretical results are justified by numerical simulations.

1. INTRODUCTION:

High dimensional data often has low-complexity structures (e.g., sparsity or low rankness). The performance of modern machine learning and data analytical methods heavily depends on appropriate low-complexity data representations (or features) which capture hidden information underlying the data. While we used to manually craft representations in the past, it has been demonstrated that learned representations from the data show much superior performance (Elad, 2010) . Therefore, (unsupervised) learning of latent representations of high-dimensional data becomes a fundamental problem in signal processing, machine learning, theoretical neuroscience and many other fields (Bengio et al., 2013) . Moreover, overcomplete representations for which the number of latent features exceeds the data dimensionality, have shown better representation of the data in various applications compared to complete representations (Lewicki & Sejnowski, 2000; Chen et al., 2001; Rubinstein et al., 2010) . In this paper, we study the following overcomplete representation learning problems.

• Overcomplete dictionary learning (ODL). One of the most important unsupervised representation learning problems is learning sparsely used dictionaries (Olshausen & Field, 1997) , which finds many applications in image processing and computer vision (Wright et al., 2010; Mairal et al., 2014) . The task is given data Y lo omo on we want to learn the compact representation (or dictionary) A P R nˆm along with the sparse code X P R mˆp . For better representation of the data, it is often more desired that the dictionary A is overcomplete m ą n, where it provides greater flexibility in matching structures in the data. • Convolutional dictionary learning (CDL). Inspired by deconvolutional networks (Zeiler et al., 2010) , the convolutional form of sparse representations (Bristow et al., 2013; Garcia-Cardona & ˚The full version of this work can be found at https://arxiv.org/abs/1912.02427.

Wohlberg, 2018) replaces the unstructured dictionary A with a set of convolution filters ta 0k u K k"1 . Namely, the problem is that given multiple circulant convolutional measurements

y i " K ÿ k"1 a 0k lo omo on filter f x ik lo omo on sparse code , 1 ď i ď p, (1.2)

one wants to learn the filters ta 0k u K k"1 along with the sparse codes. The problem resembles a lot similarities to classical ODL. Indeed, one can show that Equation (1.2) reduces to Equation (1.1) in overcomplete settings by reformulation (Huang & Anandkumar, 2015) . The interest of studying CDL was spurred by its better modeling ability of human visual and cognitive systems and the development of more efficient computational methods (Bristow et al., 2013) , and has led to a number of applications in which the convolutional form provides state-of-art performance (Gu et al., 2015; Papyan et al., 2017b; Lau et al., 2019) . Recently, the connections between CDL and convolutional neural network have also been extensively studied (Papyan et al., 2017a; 2018) . In addition, variants of finding overcomplete representations appear in many other problems beyond the dictionary learning problems we introduced here, such as overcomplete tensor decomposition (Anandkumar et al., 2017; Ge & Ma, 2017) , overcomplete ICA (Lewicki & Sejnowski, 1998; Le et al., 2011) , and short-and-sparse blind deconvolution (Zhang et al., 2017; 2018; Kuo et al., 2019) .

Prior arts on dictionary learning (DL). In the past decades, numerous heuristic methods have been developed for solving DL (Lee et al., 2007; Aharon et al., 2006; Mairal et al., 2010) . Despite their empirical success (Wright et al., 2010; Mairal et al., 2014) , theoretical understandings of when and why these methods work are still limited.

When the dictionary A is complete (Spielman et al., 2012) (i.e., square and invertible, m " n), by the fact that the row space of Y equals to that of X (i.e., rowpY q " rowpXq), Sun et al. (2016a) reduced the problem to finding the sparsest vector in a subspace (Demanet & Hand, 2014; Qu et al., 2016) . By considering a (smooth) variant of the following1 -minimization problem over the sphere,

min q 1 p › › q J Y › ›

1 , s.t. q P S n´1 , (1.3) Sun et al. (2016a) showed that the nonconvex problem has no spurious local minima when the sparsity level 1 θ P Op1q, and every local minimizer q ‹ is a global minimizer with q J ‹ Y corresponding to one row of X. The new discovery has led to efficient, guaranteed optimization methods for complete DL from random initializations (Sun et al., 2016b; Bai et al., 2018; Gilboa et al., 2019) .

However, all these methods critically rely on the fact that rowpY q " rowpXq for complete A, there is no obvious way to generalize the approach to the overcomplete setting m ą n. On the other hand, for learning incoherent overcomplete dictionaries, with sparsity θ P Op1{ ? nq and stringent assumptions on X, most of the current theoretical analysis results are local (Geng et al., 2011; Arora et al., 2015; Agarwal et al., 2016; Chatterji & Bartlett, 2017) , in the sense that they require complicated initializations that could be difficult to implement in practice. Therefore, the legitimate question remains: why do heuristic methods solve ODL with simple initializations?

Contributions. In this work we study the geometry of nonconvex landscapes for overcomplete/convolutional DL, where our result can be simply summarized by the following statement.

There exists nonconvex formulations for ODL/CDL with benign optimization landscapes, that descent methods can learn overcomplete/convolutional dictionaries with simple2 initializations.

Our approach follows the spirit of Sun et al. (2016a) , while we overcome the aforementioned obstacles for overcomplete dictionaries by directly finding columns of A instead of recovering sparse rows of X. We achieve this by reducing the problem to maximizing the4 -norm 3 of Y J q over the sphere, which is known to promote the spikiness of the solution (Zhang et al., 2018; Li & Bresler, 2018; Zhai et al., 2019) . In particular, we show the following results for ODL and CDL, respectively. 1. For the ODL problem, when A is unit norm tight frame and incoherent, our nonconvex objective is strict saddle (Ge et al., 2015; Sun et al., 2015b) in the sense that any saddle point can be escaped by negative curvature and all local minimizers are globally optimal. Furthermore, every local minimizer is close to a column of A.

2. For the CDL problem, when the filters are self and mutual incoherent, a similar nonconvex objective is strict saddle over a sublevel set, within which every local minimizer is close to a target solution. Moreover, we develop a simple data-driven initialization that falls into this sublevel set. Our analysis on ODL provides the first global characterization for nonconvex optimization landscape in the overcomplete regime. On the other hand, our result also gives the first provable guarantee for CDL. Indeed, under mild assumptions, our landscape analysis implies that with simple initializations, any descent method with the ability of escaping strict saddle points 4 provably finds global minimizers that are close to our target solutions for both problems. Moreover, our result opens up several interesting directions on nonconvex optimization that are worth of further investigations.

2. OVERCOMPLETE DICTIONARY LEARNING:

In this section, we start stating our result with ODL. In Section 3, we will show how our geometric analysis here can be extended to CDL in a nontrivial way.

2.1. BASIC ASSUMPTIONS:

We study the DL problem in Equation (1.1) under the following assumptions for A P R nˆm and X P R mˆp . In particular, our assumption for the dictionary A can be viewed as a generalization of orthogonality in the overcomplete setting (Mixon, 2016) . Assumption 2.1 (Tight frame and incoherent dictionary A) We assume that the dictionary A is unit norm tight frame (UNTF) (Mixon, 2016) , in the sense that n m AA J " I, }a i } " 1 p1 ď i ď mq, (2.1)

and its columns satisfy the µ-incoherence condition. Namely, let A " ra 1 a 2 ¨¨¨a m s, µpAq :" max 1ďi "jďm ˇˇˇB a i }a i } , a j }a j } FˇˇˇˇP p0, 1q.

(2.2)

We assume the coherence of A is small, i.e., µpAq ! 1.

Assumption 2.2 (Random Bernoulli-Gaussian X) We assume entries of X " i.i.d. BGpθq5 , that

X " B d G, B ij " i.i.d. Berpθq, G ij " i.i.d. N p0, 1q,

where the Bernoulli parameter θ P p0, 1q controls the sparsity level of X.

Remark 1. The coherence parameter µ plays an important role in shaping the optimization landscape. A smaller coherence µ implies that the columns of A are less correlated, and hence easier for optimization. For matrices with 2 -normalized columns, classical Welch bound (Welch, 1974; Foucart & Rauhut, 2013a) suggests that the coherence µ is lower bounded by µpAq ě b m´n pm´1qn , which is achieved when A is equiangular tight frame (Sustik et al., 2007) . For a generic random6 matrix A, w.h.p. it is approximately UNTF, with coherence µpAq « b log m n roughly achieving the order of Welch bound. For a typical dictionary A under Assumption 2.1, this suggests that the coherence parameter µpAq often decreases w.r.t. the feature dimension n. Both function values are normalized to r0, 1s. The overcomplete dictionary A is generated to be UNTF, with n " 3 and m " 4.

The sparse coefficient X " BGpθq with θ " 0.1 and p " 2 ˆ10 4 . Black dots denote columns of A (target).

Figure 2 : Spikiness pζq vs. }ζ} 4 4 { }q} 4 . We generate UNTF A, randomly draw many points q P S n´1 , and compute }ζ} 4 4 and spikiness pζq as in (2.6) with ζ " A J q. On the plot, we mark each point q P S n´1 by "`".

2.2. PROBLEM FORMULATION:

We solve DL in the overcomplete regime by considering the following problem min q ϕ DL pqq :" ´cDL p

EQUATION

where c DL ą 0 is a normalizing constant. At the first glance, our objective looks similar to Equation (1.3) in complete DL, but we tackle the problem from a very different aspect -we directly find columns of A instead of recovering sparse rows of X. Given UNTF A and random X " BGpθq, our intuition of solving Equation (2.3) originates from the fact (Lemma D.1) E X rϕ DL pqqs " ϕ T pqq ´θ 2p1 ´θq ´m n ¯2 , ϕ T pqq :" ´1 4

EQUATION

where ϕ T pqq can be viewed as the objective for 4th order tensor decomposition in Ge & Ma (2017) . When p is large, this tells us that optimizing Equation (2.3) is approximately maximizing 4 -norm of ζ " A J q over the sphere (see Figure 1 ). If q equals to one of the target solutions (e.g., q " a 1 ),

ζpqq :" A J q " " }a 1 } 2 lo omo on "1 a J 1 a 2 lo omo on |¨| ă µ ¨¨¨a J 1 a m lo omo on |¨| ă µ  J , (2.5)

then ζ is spiky when µ is small (e.g., µ ! 1). with 2 -norm fixed. This implies that maximizing 4 -norm over the sphere promotes the spikiness of ζ (Zhang et al., 2018; Li & Bresler, 2018; Zhai et al., 2019) . Thus, from Equation (2.5), we expect the global minimizer q ‹ of Equation (2.3) is close to one column of A. Ge & Ma (2017) proved that for ϕ T pqq there is no spurious local minimizer below a sublevel set whose measure over S n´1 geometrically shrinks w.r.t. the dimension n, and without providing valid initialization into the set. Therefore, the challenge still remains: can simple descent methods solve the nonconvex objective Equation (2.3) to global optimality? In this work, we show that the answer is affirmative. Under proper assumptions, we show that our objective actually has benign global geometric structure, explaining why descent methods with random initialization solve the problem to the target solutions.

2.3. GEOMETRIC ANALYSIS OF NONCONVEX OPTIMIZATION LANDSCAPE:

To characterize the landscape of ϕ DL pqq over the sphere S n´1 , let us first introduce some basic tools from Riemannian optimization (Absil et al., 2009a) . For any function f : S n´1 Þ Ñ R, we have grad f pqq :" P q K ∇f pqq, Hess f pqq :" P q K `∇2 f pqq ´xq, ∇f pqqy I ˘Pq K to be the Riemannian gradient and Hessian7 of f pqq. In addition, we partition S n´1 into two regions R N :"

! q P S n´1 ˇˇϕ T pqq ě ´ξDL µ 2{3 }ζpqq} 2 3 ) , (2.7) R C :" ! q P S n´1 ˇˇϕ T pqq ď ´ξDL µ 2{3 }ζpqq} 2 3 ) , (2.8)

for some fixed numerical constant ξ DL ą 0. Unlike the approach in Sun et al. (2016a) , our partition and landscape analysis are based on function value ϕ T pqq instead of target solutions. This is because in overcomplete case the optimization landscape is more irregular compared to that of the complete/orthogonal case, which introduces extra difficulties for explicit partition of the sphere. In particular, for each region we show the following results. Theorem 2.3 (Global geometry of nonconvex landscape for ODL) Suppose we have

K :" m{n, θ P `m´1 , 3 ´1˘, ξ DL ą 2 6 , µ P `0, 40 ´1˘,

(2.9)

and assume Y " AX such that A and X satisfy Assumption 2.1 and Assumption 2.2, respectively. 1. (Negative curvature in R N ) W.h.p. over the randomness of X, whenever p ě CθK 4 n 6 logpθn{µq and K ď 3 ¨´1 `6µ `6ξ 3{5 DL µ 2{5 ¯´1 , any point q P R N exhibits negative curvature in the sense that

D v P S n´1 , s.t. v J Hess ϕ DL pqqv ď ´3 }ζ} 4 4 }ζ} 2 8 .

2. (No bad critical points in R C ) W.h.p. over the randomness of X, whenever

p ě CθK 3 max µ ´2, Kn 2 ( n 3 logpθn{µq and K ď ξ 3{2 DL {8,

every critical point q c of ϕ DL pqq in R C is either a strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a 1 ) such that

xa 1 { }a 1 } , q c y ě 1 ´5ξ ´3{2 DL .

Here C ą 0 is a universal constant.

Remark 2. A combination of our geometric analysis for both regions provides the first global geometric analysis for ODL with θ P Op1q, which implies that ϕ DL pqq has no spurious local minimizers over S n´1 : any critical point is either a strict saddle point that can be efficiently escaped, or it is near one of the target solutions. Moreover, recent results show that nonconvex problems with this type of optimization landscapes can be solved to optimal solutions by using (noisy) gradient descent methods with random initializations (Lee et al., 2016; Jin et al., 2017; Lee et al.; Criscitiello & Boumal, 2019) . In addition, we point out several limitations of our result for future work.

• As we have only characterized properties of critical points, our result does not directly lead to convergence rate for descent methods. To show polynomial-time convergence, as suggested by Sun et al. (2016a; 2018) ; Li & Bresler (2018) ; Kuo et al. (2019) , we need finer partitions of the sphere and uniform controls of derivatives in each region8 . We leave this for future work.

• Our analysis in R N says that when µ is sufficiently small9 the maximum overcompleteness K allowed is roughly K " 3, which is smaller than that of R C (which could be a large constant). We believe this is mainly due to loose bounds for controlling norms of A in R C . Moreover, our experiment result in Section 4 suggests that there is a substantial gap of K between our theory and practice: the phase transition in Figure 3a shows that gradient descent with random initialization works even in the regime m ď n 2 . We leave improvement of our result as an open question.

Brief sketch of analysis. From Equation (2.4), we know that ϕ DL pqq reduces to ϕ T pqq in large sample limit as p Ñ 8. This suggests an expectation and concentration type of analysis: (i) we first characterize critical points and negative curvature for the deterministic function ϕ T pqq in R C and R N (see Appendix B); (ii) for any small δ ą 0, we show the measure concentrates in the sense that for a finitely large p ě r Ωpδ ´2polypnqq,

sup qPS n´1 }grad ϕ DL pqq ´grad ϕ T pqq} ď δ, sup qPS n´1

}Hess ϕ DL pqq ´Hess ϕ T pqq} ď δ holds w.h.p. over the randomness of X. Thus we can turn our analysis of ϕ T pqq to that of ϕ DL pqq by a perturbation analysis (see Appendix C & D). Here, it should be noticed that grad ϕ DL pqq and Hess ϕ DL pqq are 4th-order polynomials of X, which are heavy-tailed empirical processes over q P S n´1 . To control suprema of heavy-tailed processes, we developed a general truncation and concentration type of analysis similar to Zhang et al. (2018) ; Zhai et al. (2019) , so that we can utilize classical bounds for sub-exponential random variables (Boucheron et al., 2013) (see Appendix F).

3. CONVOLUTIONAL DICTIONARY LEARNING:



Recall from Section 1, the basic task of CDL is that given convolutional measurements in the form of Equation (1.2), we want to recover kernels ta 0k u K k"1 . Here, by reformulating10 CDL in the form of ODL, we generalize our analysis from Section 2.3 to CDL with a few new ingredients.

Reduction from CDL to ODL. For any z P R n , let C z P R nˆn be the circulant matrix generated from z. From Equation (1.2), the properties of circulant matrix imply that

C yi " C ř K k"1 a 0k fx ik " K ÿ k"1 C a 0k C x ik " A 0 ¨Xi , 1 ď i ď p, with A 0 " rC a01 C a02 ¨¨¨C a 0K s and X i " " C J xi1 C J xi2 ¨¨¨C J

x iK ‰ J , so that A 0 P R nˆnK is overcomplete and structured. Thus, contencating all C yi , we have

" C y1 C y2 ¨¨¨C yp ‰ loooooooooooooomoooooooooooooon Y PR nˆnp " A 0 ¨rX 1 X 2 ¨¨¨X p s loooooooooooomoooooooooooon XPR nKˆnp ùñ Y " A 0 ¨X.

This suggests that we can view the CDL problem as ODL: if we can recover a column of the overcomplete dictionary A 0 , we find one of the filters a 0k p1 ď k ď Kq up to a circulant shift11 .

Nonconvex problem formulation and preconditioning. To solve CDL, one may consider the same objective Equation (2.3) as ODL. However, for many applications our structured dictionary A 0 could be badly conditioned and not tight frame, which results in bad optimization landscape and even spurious local minimizers. To deal with this issue, we whiten our data Y by preconditioning12 

P Y " P A 0 X, P " " `θK 2 np ˘´1 Y Y J ı ´1{2 . (3.1)

For large p, we approximately have

P « `K´1 A 0 A J 0 ˘´1{2 (see Appendix E.5), so that P Y « `K´1 A 0 A J 0 ˘´1{2 A 0 ¨X " A ¨X, A :" `K´1 A 0 A J 0 ˘´1{2 A 0 ,

where A is automatically tight frame with K ´1AA J " I. This suggests to consider

min q ϕ CDL pqq :" ´cCDL np › › q J pP Y q › › 4 4 , s.t. }q} 2 " 1, (3.2)

Algorithm 1 Finding one filter with data-driven initialization

Input: data Y P R nˆp Output: an esimated filter a ‹ 1: preconditioning. Cook up the preconditioning matrix P in Equation (3.1). 2: initialization. Initialize q init " P S n´1 pP y q with a random sample y , 1 ď ď p.

3: optimization with escaping saddle points. Optimize Equation (3.2) to a local minimizer q ‹ , by using a descent method such as Goldfarb et al. (2017) that escapes strict saddle points. 4: return an estimated filter a ‹ " P S n´1 `P ´1q ‹ ˘.

for some normalizing constant c CDL ą 0, so that is close to optimizing

p ϕ CDL pqq :" ´cCDL np › › q J AX › › 4 4 « ϕ CDL pqq,

for a tight frame dictionary A (we make this rigorous in Appendix E.4). To study the problem, we make assumptions on the sparse signals x ik " i.i.d. BGpθq similar to Assumption 2.2. Furthermore, we assume A 0 and A satisfy the following properties which serve as counterparts to Assumption 2.1.

Assumption 3.1 (Properties of A 0 and A) We assume the filter matrix A 0 has minimum singular value σ min pA 0 q ą 0 with bounded condition number κpA 0 q :" σ max pA 0 q{σ min pA 0 q. In addition, we assume the columns of A are mutually incoherent: max i "j ˇˇA ai }ai} ,

aj }aj } Eˇˇˇď µ.

3.2. GEOMETRIC ANALYSIS AND NONCONVEX OPTIMIZATION:

Optimization landscape for CDL. We characterize the geometric structure of ϕ CDL pqq over R CDL :"

EQUATION

for some fixed numerical constant ξ CDL ą 0, where ζpqq " A J q and ϕ T pqq " ´4´1 }ζpqq} 4 4 as introduced in Equation (2.4). We show ϕ CDL pqq satisfies the following properties.

Theorem 3.2 (Local geometry of nonconvex landscape for CDL) Let us denote m :" Kn, and let C 0 ą 5 and η ă 2 ´6 be some positive constants. Suppose we have

θ P `m´1 , 3 ´1˘, ξ CDL " C 0 ¨η´2{3 , µ P `0, 40 ´1˘,

and assume that Assumption 3.1 and x ik " i.i.d. BGpθq hold. There exists some constant C ą 0, w.h.p. over the randomness of x ik s, whenever p ě CθK 2 µ ´2n 4 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q

, n * log 6 pn{µq and K ă C 0 , every critical point q c in R CDL is either a strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a 1 ) such that xa 1 { }a 1 } , q c y ě 1 ´5κ ´2η.

Remark 3. The analysis is similar to that of ODL in R C (see Appendix D). In contrast, our sample complexity p and R CDL have extra dependence on κpA 0 q due to preconditioning in Equation (3.1).

On the other hand, because our preconditioned dictionary A is tight frame but not necessarily UNTF, in the worst case we cannot exclude existence of spurious local minima in R c CDL Ş S n´1 for CDL. From geometry to optimization. Nonetheless, in Algorithm 1 we propose a simple data-driven initialization q init such that q init P R CDL . Since R CDL does not have bad local minimizers, by proving that all iterates stay within R CDL , it suffices to show global convergence of Algorithm 1. We initialize q by randomly picking a preconditioned data sample P y with P rps, and set q init " P S n´1 pP y q , s.t. ζ init " A J q init « ? KP S nK´1 `AJ Ax ˘.

(3.4)

For generic A, small µpAq implies that A J A is close to a diagonal matrix13 , so that ζ init is spiky for sparse x . Therefore, we expect large }ζ init } 4 4 and q init P R CDL by leveraging sparsity of x . 

c 1 log m m ď θ ď c 2 µ ´2{3 κ 4{3 m log m ¨min " κ 4{3 µ 4{3 , Kµ ´4 m 2 log m * .

(3.5) W.h.p. over the randomness of x ik s, whenever p ě CθK 2 µ ´2 max K 6 κ 6 pA 0 q{σ 2 min pA 0 q, n ( n 4 log 6 pm{µq ,

we have q init P R CDL , and all future iterates of Algorithm 1 stay within R CDL and converge to an approximate solution (e.g., some circulant shift s ra 01 s of a 0k with 1 ď ď n) in the sense that

› › P S n´1 `P ´1q ‹ ˘´s ra 01 s › › ď ,

where is a small numerical constant. Here, c 1 , , c 2 , C ą 0 are some numerical constants.

Remark 4. Our result (Equation (3.5)) suggests that there is a tradeoff between µ and θ for optimization. For generic filters (e.g. drawn uniformly from the sphere), we approximately have14 µ P r Opm ´1{2 q and κ P Op1q, so that our theory suggests the maximum sparsity allowed is θ P r Opm ´2{3 q. For other smoother filters which may have larger µ and κ, the sparsity θ allowed tends to be smaller. Improving Equation (3.5) is the subject of future work. On the other hand, our result guarantees convergence to an approximate solution of constant error. We left exact recovery for future work. Finally, although we write CDL in the matrix-vector form, the optimization could be implemented very efficiently using fast Fourier transform (FFT) (see Appendix G).

4. EXPERIMENTS:

In this section, we experimentally demonstrate our proposed formulation and approach for ODL and CDL. We solve our nonconvex problems in Equation (2.3) and Equation (3.2) using optimization methods15 with random initializations introduced in Appendix G.

Experiments on ODL. We generate data Y " AX, with dictionary A P R nˆm being UNTF16 , and sparse code X P R mˆp " i.i.d. BGpθq. To judge the success recovery of one column of A, let ρ e " min 1ďiďm p1 ´|xq ‹ , a i { }a i }y|q .

We have ρ e " 0 when q ‹ " P S n´1 pa i q, thus we assume a recovery is successful if ρ e ă 5 ˆ10 ´2.

• Overcompleteness. First, we fix θ " 0.1, and test the limit of the overcompleteness K " m{n we can achieve by plotting the phase transition on pm, nq in log scale. To get rid of the influence of sample complexity p, we run our algorithm on ϕ T pqq which is the sample limit of ϕ DL pqq. For each pair of pm, nq, we repeat the experiment for 12 times. As shown in Figure 3a , it suggests that the limit of overcompleteness is roughly m « n 2 , which is much larger than our theory predicts. • Recovering full matrix A. Second, although our theory only guarantees recovery of one column of A, Figure 3b suggests that we can recover the full dictionary A by repetitive independent trials. As the result shows, Opm log mq independent runs suffice to recover the full A. • Recovery with varying θ and p. Our simulation in Figure 3c implies that we need more samples p when the overcompleteness K increases. Meanwhile, Figure 3d shows successful recovery even when sparsity θ « 0.3. The maximum θ seems to remain as a constant when n increases.

Experiments on CDL. Finally, for CDL, we generate measurement according to Equation (1.2) with K " 3, where the filters ta 0k u K k"1 are drawn uniformly from the sphere S n´1 , and x ik " i.i.d. BGpθq. Figure 4 shows that our method can approximately recover all the filters by running a few number of repetitive independent trials.

5. CONCLUSION AND DISCUSSION:

In this work, we showed that nonconvex landscapes of overcomplete representation learning also possess benign geometric structures. In particular, by reducing the problem to an 4 optimization problem over the sphere, we proved that ODL has no spurious local minimizers globally: every critical point is either an approximate solution or a saddle point can be efficiently escaped. Moreover, we showed that this type of analysis can be carried over to CDL with a few new ingredients, leading to the first provable method for solving CDL globally. Our results have opened several interesting questions that are worth of further investigations, that we discuss as follows.

Tighter bound on overcompleteness for ODL. As shown in Theorem 2.3, our bound on the overcompleteness K " m{n is an absolute constant, which we believe is far from tight (see experiments in Figure 3a ). In the high overcompleteness regime (e.g., n ! m ď n 2 ), one conjecture is that spurious local minimizer does exist but descent methods with random initializations implicitly regularizes itself such that bad regions are automatically avoided Ma et al. (2017) ; another conjecture is that there is actually no spurious local minimizers. We tend to believe the latter conjecture is true. Indeed, the looseness of our analysis appears in the region R N (see Appendix B.2), for controlling the norms of A.

One idea might be to consider i.i.d. Gaussian dictionary instead of the deterministic incoherent dictionary A, and use probabilistic analysis instead of the worst-case deterministic analysis. However, our preliminary analysis suggests that elementary concentration tools for Gaussian empirical processes are not sufficient to achieve this goal. More advanced probabilistic tools might be needed here.

Another idea that might be promising is to leverage more advanced tools such as the sum of squares (SoS) techniques Lasserre (2001); Blekherman et al. (2012) . Previous results Barak et al. (2015) ; Ma et al. (2016); Hopkins et al. (2015) used SoS as a computational tool for solving this type of problems, while the computational complexity is often quasi-polynomial and hence cannot handle problems of large-scale. In contrast, our idea here is to use SoS to verify the geometric structure of the optimizing landscape instead of computation, to have a better uniform control of the negative curvature in R N . If we succeeded, this might lead to a tighter bound on the overcompleteness. Moreover, analogous to building dual certificates for convex relaxations such as compressive sensing Candès & Wakin (2008) ; Candes & Plan (2011) and matrix completion Candès & Recht (2009); Candès et al. (2011) , it could potentially lead to a more general approach for verifying benign geometry structures for nonconvex optimization.

Composition rules for nonconvex optimization? Another interesting phenomenon we found through understanding ODL is that under certain scenarios the benign nonconvex geometry can be preserved under nonnegative addition. Indeed, if we separate our dictionary A into several subdictionaries as A " rA 1 ¨¨¨A N s, then the asymptotic version of nonconvex objective for ODL (Equation (2.3)) can be rewritten as

ϕ T pqq " ´1 4 › › A J q › › 4 4 " N ÿ k"1 ϕ k T pqq, ϕ k T pqq :" ´1 4 › › A J k q › › 4 4 p1 ď k ď N q.

(5.1)

Presumably, every function ϕ k T pqq also possess benign geometry for each submatrix A k . This discovery might suggest more general properties in nonconvex optimization -benign geometry structures can be preserved under certain composition rules. Analogous to the study of convex functions Boyd & Vandenberghe (2004) , discovering composition rules can potentially lead to simpler analytical tools for studying nonconvex optimization problems and hence have broad impacts.

Finding all components over Stiefel or Oblique manifolds. The nonconvex formulations considered in this work is only guaranteed to recover one column/filter at a time for ODL/CDL. Although our experimental results in Section 4 implies that the full dictionary or all the filters can be recovered by using repetitive independent trials, it is more desirable to have a formulation that can recover the whole dictionary/filters in one shot. This requires us to consider optimization problems constraint over more complicated manifolds rather than the sphere, such as Stiefel and Oblique manifolds Absil et al. (2009a) . Despite of recent empirical evidences Lau et al. (2019) ; Li et al. (2019) and study of local geometry Zhai et al. (2019) ; Zhu et al. (2019) , more technical tools need to be developed towards better understandings for nonconvex problems constraint over these more complicated manifolds.

Miscellaneous. Finally, we summarize several small questions that might be also worth of pursuing. • Designing better loss functions. The 4 objective we considered here for ODL and CDL is heavy-tailed for sub-Gaussian random variables, resulting in bad sample complexity and large approximation error. It would be nice to design better loss functions that also promotes spikiness of the solutions. • Non-asymptotic convergence for descent methods. Unlike the results in Sun et al. (2016a; c) ; Kuo et al. (2019) , our geometric analysis here does not directly lead to non-asymptotic convergence guarantees of any descent methods to global minimizers. This is because we only characterized the geometric properties of critical points on the function landscape. To show non-asymptotic convergence of methods introduced in Appendix G, we need to uniformly characterize the geometric properties over the sphere. • Finer models for CDL. Finally, for CDL, it is worth noting that in many cases the length of the filters ta 0k u K k"1 is often much shorter than the observations ty i u 2019), which has not been considered in this work. The extra structure leads to the so-called short-and-sparse CDL Lau et al. (2019) , where the lower dimensional model can lead to fewer samples for recovery. Based on our results, we believe the short structure can be dealt with by developing finer analysis such as that in Kuo et al. (2019) .

ACKNOWLEDGEMENT:

Part of this work was done when QQ and YXZ were at Columbia University. QQ thanks the generous support of the Microsoft graduate research fellowship and Moore-Sloan fellowship. XL would like to acknowledge the support by Grant CUHK14210617 from the Hong Kong Research Grants Council. YQZ is grateful to be supported by NSF award 1740822. ZZ was partly supported by NSF Grant 1704458. The authors would like to thank Joan Bruna (NYU Courant), Yuxin Chen (Princeton University), Lijun Ding (Cornell University), Han-wen Kuo (Columbia University), Shuyang Ling (NYU Shanghai), Yi Ma (UC Berkeley), Ju Sun (University of Minnesota, Twin Cities), René Vidal (Johns Hopkins University), and John Wright (Columbia University) for helpful discussions and inputs regarding this work.

APPENDIX:

The Appendix is organized as follows. In Appendix A, we introduce the basic notations and technical tools for analysis. Appendix B provides a determinsitic characterization of the optimization landscape in population. In Appendix C, we turn our analysis of Appendix B into finite sample version. Appendix D and Appendix E provide the detailed proof for ODL and CDL, respectively. The detailed concentration bounds are postponed to Appendix F. Finally, Appendix G provides some ideas of optimization methods.

A NOTATIONS AND BASIC TOOLS:

A.1 BASIC NOTATIONS Throughout this paper, all vectors/matrices are written in bold font a/A; indexed values are written as a i , A ij . We use S n´1 to denote an n-dimensional unit sphere in the Euclidean space R n . We let rms " t1, 2, ¨¨¨, mu. We use d to denote Hadamard product between two vectors/matrices. For v P R n , we use v dr to denote entry-wise power of order m, i.e., v dr " rv r 1 , ¨¨¨, v r n s J . Let F n P C nˆn denote a unnormalized n ˆn DFT matrix, with }F n } " ? n, and F ´1 n " n ´1F n . In many cases, we just use F to denote the DFT matrix. Some basic operators. We use P v and P v K to denote projections onto v and its orthogonal complement, respectively. We let P S n´1 to be the 2 -normalization operator. To sum up, we have

P v K u " u ´vv J }v} 2 v, P v u " vv J }v} 2 u, P S n´1 v " v }v} .

Circular convolution and circulant matrices. The convolution operator f is circular with modulo-m: pa f xq i " ř m´1 j"0 a j x i´j . For v P R m , let s rvs denote the cyclic shift of v with length . Thus, we can introduce the circulant matrix

C v P R mˆm generated through v P R m , C v " » - - - - - - v 1 v m ¨¨¨v 3 v 2 v 2 v 1 v m v 3 . . . v 2 v 1 . . . . . . v m´1 . . . . . . v m v m v m´1 ¨¨¨v 2 v 1 fi ffi ffi ffi ffi ffi fl

" rs 0 rvs s 1 rvs ¨¨¨s m´1 rvss .

(A.1)

Now the circulant convolution can also be written in a simpler matrix-vector product form. For instance, for any u P R m and v

P R m , u f v " C u ¨v " C v ¨u, C ufv " C u C v .

In addition, the correlation between u and v can be also written in a similar form of convolution operator which reverses one vector before convolution.

Basics of Riemannian derivatives. Here, we give a brief introduction to manifold optimization over the sphere, and the forms of Riemannian gradient and Hessian. We refer the readers to the book (Absil et al., 2009b) for more backgrounds. Given a point q P S n´1 , the tangent space T q S n´1 is defined as T q S n´1 . " v | v J q " 0 ( . Therefore, we have the projection onto T q S n´1 equal to P q K . For a function f pqq defined over S n´1 , we use grad f and Hess f to denote the Riemannian gradient and the Hessian of f , then we have grad f pqq .

" P q K ∇f pqq, Hess f pqq . " P q K `∇2 f pqq ´xq, ∇f pqqy I ˘Pq K ,

where ∇f pqq and ∇ 2 f pqq are the normal first and second derivatives in Euclidean space. For example, for the function ϕ T pqq defined in Equation (2.4), direct calculations give that

grad ϕ T pqq " ´Pq K A `AJ q ˘d3 " ´Pq K m ÿ k"1 `aJ k q ˘3 a k , Hess ϕ T pqq " ´Pq K " 3A diag ´`A J q ˘d2 ¯AJ ´› › A J q › › 4 4 I ı P q K .

A.2 BASIC TOOLS:

Lemma A.1 (Norm Inequality) If p ą r ą 0, then for x P R n , we have }x} p ď }x} r ď n 1{r´1{p }x} p .

Lemma A.2 Let z, r P R. We have p1 `zq r ď 1 `p2 r ´1qz, @ z P r0, 1s, r P Rzp0, 1q, p1 `zq r ď 1 `rz, @ z P r´1, `8q, r P r0, 1s, where the second inequality reverse when r P Rzp0, 1q.

Lemma A.3 (Moments of the Gaussian Random Variable) If X " N `0, σ 2 X ˘, then it holds for all integer m ě 1 that E r|X| m s ď σ m X pm ´1q!!, k " tm{2u.

Lemma A.4 (Noncentral moments of the χ Random Variable) If Z " χ pmq, then it holds for all integer p ě 1 that

E rZ p s " 2 p{2 Γ pp{2 `m{2q Γ pm{2q ď p!! m p{2 .

Lemma A.5 (Bernstein's Inequality for R.V.s (Foucart & Rauhut, 2013b )) Let X 1 , . . . , X p be i.i.d. real-valued random variables. Suppose that there exist some positive numbers R and σ 2

X:

such that

E r|X k | m s ď m! 2 σ 2 X R m´2 , for all integers m ě 2. Let S . " 1 p ř p k"1 X k , then for all t ą 0, it holds that P r|S ´E rSs| ě ts ď 2 exp ˆ´pt 2 2σ 2 X `2Rt ˙.

Lemma A.6 (Bernstein's Inequality for Random Vectors (Sun et al., 2015a )) Let x 1 , . . . , x p P R d be i.i.d. random vectors. Suppose there exist some positive number R and σ 2 X such that

E r}x k } m s ď m! 2 σ 2 X R m´2

, for all integers m ě 2.

Let s " 1 p ř p k"1 x k , then for any t ą 0, it holds that

P r}s ´E rss} ě ts ď 2pd `1q exp ˆ´pt 2 2σ 2 X `2Rt ˙.

Lemma A.7 (Bernstein's Inequality for Bounded R.M.s, Theorem 1.6.2 of Tropp et al. ( 2015)) Let X 1 , X 2 , ¨¨¨, X p P R d1ˆd2 be i.i.d. random matrices. Suppose we have

}X i } ď R almost surely, max › › E " X i X J i ‰› › , › › E " X J i X i ‰› › ( ď σ 2 X , 1 ď i ď p. Let S " 1 p ř p i"1 X i , then we have P p}S ´E rSs} ě tq ď pd 1 `d2 q exp ˆ´pt 2 2σ 2 X `4Rt{3 ˙.

Lemma A.8 (Bernstein's Inequality for Bounded Random Vectors) Let x 1 , x 2 , ¨¨¨, x p P R d be i.i.d. random vectors. Suppose we have

}x i } ď R almost surely, E " }x i } 2 ı ď σ 2 X , 1 ď i ď p.

Let s " 1 p ř p i"1 x i , then we have

P p}s ´E rss} ě tq ď d exp ˆ´pt 2 2σ 2 X `4Rt{3 ˙.

Lemma A.9 (Lemma A.4 of (Zhang et al., 2018) ) Let v P R d with each entry following i.i.d.

Berpθq distribution, then

P p|}v} 0 ´θd| ě tθdq ď 2 exp ˆ´3t 2 2t `6 θd ˙.

Lemma A.10 (Matrix Perturbation Bound, Lemma B.12 of (Qu et al., 2019) ) Suppose B ą 0 is a positive definite matrix. For any symmetric perturbation matrix ∆ with }∆} ď 1 2 σ min pBq, it holds that

› › ›pB `∆q ´1{2 ´B´1{2 › › › ď 4 }∆} σ 2 min pBq , › › ›pB `∆q 1{2 B ´1{2 ´I› › › ď 4 }∆} σ 3{2 min pBq

, where σ min pBq denotes the minimum singular value of B.

Lemma A.11 For any q, q 1 , q 2 P S n´1 , we have

› › P q K › › ď 1, }P q1 ´Pq2 } ď 2 }q 1 ´q2 } .

Proof The first is obvious, and for the second inequality we have

› › ›P q K 1 ´Pq K 2 › › › " › › q 1 q J 1 ´q2 q J 2 › › ď › › q 1 q J 1 ´q1 q J 2 › › `› › q 1 q J 2 ´q2 q J 2 › › ď 2 }q 1 ´q2 } , as desired.

Lemma A.12 For any nonzero vectors u and v, we have

› › › › u }u} ´v }v} › › › › ď 2 }v} }u ´v} . Proof We have › › › › u }u} ´v }v} › › › › " 1 }u} }v} › › }v} u ´}u} v › › " 1 }u} }v} › › }v} u ´}v} v `}v} v ´}u} v › › ď 1 }u} }v} p}v} }u ´v} `}v} |}u} ´}v}|q ď 2 }u} }u ´v} ,

as desired.

B ANALYSIS OF ASYMPTOTIC OPTIMIZATION LANDSCAPE:

In this part of the appendix, we present the detailed analysis of the optimization landscape of the asymptotic objective

min q ϕ T pqq " ´1 4 › › A J q › › 4 4 , s.t. q P S n´1

over the sphere. We denote the overcompleteness of the dictionary A P R nˆm and the correlation of columns of A with q by K :" m n , ζpqq :" A J q " rζ 1 ¨¨¨ζ m s J .

Without loss of generality, for a given q P S n´1 , we assume that

|ζ 1 | ě |ζ 2 | ě ¨¨¨ě |ζ m | .

Assumption. We assume that the dictionary A is tight frame with 2 -norm bounded columns

1 K AA J " I, }a i } ď M p1 ď i ď mq. (B.1)

We also assume that the columns of A satisfy the µ-incoherence condition. Namely, we have

µpAq :" max 1ďi "jďm ˇˇˇB a i }a i } , a j }a j } FˇˇˇˇP p0, 1q, (B.2)

such that µ is sufficiently small. Based on the function value of the objective ϕ T pqq, we partition the sphere into two regions

R C pq; ξq " ! q P S n´1 | }ζ} 4 4 ě ξµ 2{3 }ζ} 2 3 ) , (B.3) R N pq; ξq " ! q P S n´1 | }ζ} 4 4 ď ξµ 2{3 }ζ} 2 3 ) , (B.4)

where ξ ą 0 is some scalar. In the following, for appropriate choices of K, µ, and ξ, we first show that R C does not have any spurious local minimizers by characterizing all the critical points within the region. Second, under more stringent condition that A is 2 column normalized, for the region R N we show that there exhibits large negative curvature throughout the region, such that there is no local/global minimizer within R N .

B.1 GEOMETRIC ANALYSIS OF CRITICAL POINTS IN R C:

In this subsection, we show that all the critical points of ϕ T pqq in R C are either ridable saddle points, or satisfy second-order optimality condition and are close to the target solutions.

Proposition B.1 Suppose we have

KM ă 4 ´1 ¨ξ3{2 , M 3 ă η ¨ξ3{2 , µ ă 1 20 (B.5)

for some constant η ă 2 ´6. Then any critical point q P R C , with grad ϕ T pqq " 0, either is a ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components e.g., a 1 in the sense that

B a 1 }a 1 } , q F ě 1 ´5ξ ´3{2 M 3 ě 1 ´5η.

First, in Appendix B.1.1 we characterize some basic properties of critical points of ϕ T pqq. Based on this, we prove Proposition B.1 in Appendix B.1.2.

B.1.1 BASIC PROPERTIES OF CRITICAL POINTS:

Lemma B.2 (Properties of critical points) For any point q P S n´1 , if q is a critical point of ϕ T pqq over the sphere, then it satisfies

f pζ i q " ζ 3 i ´αi ζ i `βi " 0 (B.6)

for all i P rms with ζpqq " A J q, where

α i :" }ζ} 4 4 }a i } 2 , β i :" ř j‰i xa i , a j y ζ 3 j }a i } 2 . (B.7)

Proof For any point q P S n´1 , if q is a critical point of ϕ T pqq over the sphere, then its Riemannian gradient satisfies grad ϕ T pqq " P q K Aζ d3 " 0 ùñ Aζ d3 ´}ζ} 4 4 q " 0. Multiple a J i (1 ď i ď m) on both sides of the equality, we obtain Since the roots of f pzq correspond to the critical points of ϕ T pqq, we characterize the properties of the roots as follows.

}a i } 2 ζ 3 i ´}ζ} 4 4 ζ i `ÿ j‰i xa i , a j y ζ 3 j " 0. √ α - √ α z f (z) f ( √ α) f (- √ α) O 2β α √ α -2β α - √ α -2β α f (- √ α -2β α ) f ( √ α -2β α ) f ( 2β α ) f (0) f (z) = β

Lemma B.3 Consider the following cubic polynomial f pzq "

z 3 ´αz `β (B.8) with 0 ă |β| ď 1 4 α 3{2 , α ą 0. (B.9)

Then the roots of the function f pzq is contained in one of the nonoverlapping intervals:

I 1 :" " z P R ˇˇˇ| z| ď 2 |β| α * , I 2 :" " z P R ˇˇˇˇz ´?α ˇˇď 2 |β| α * , I 3 :" " z P R ˇˇˇˇz `?α ˇˇď 2 |β| α * .

Proof By our construction |β| ď 1 4 α 3{2 and α ą 0 in Equation (B.9), it is obvious that the intervals I 1 , I 2 , and I 3 are nonoverlapping. Without loss of generality, let us assume that β is positive. We have f p ? αq " f p´?αq " f p0q " β ą 0. (B.10) Thus, as illustrated in Figure 5 , if we can show that

f ˆ2β α ˙ă 0, f ˆ´? α ´2β α ˙ă 0, f ˆ?α ´2β α ˙ă 0, (B.11)

then this together with Equation (B.10) suffices to show that there exists at least one root in each of the three intervals I 1 , I 2 , and I 3 . Next, we show Equation (B.11) by direct calculations. First, notice that 

f ˆ2β α ˙" ˆ2β α ˙3 ´β " β α 3 `8β 2 ´α3 ˘" β α 3 ˆ1 2 α 3 ´α3 ˙ď ´1 2 β ă 0, Second, we have f ˆ´? α ´2β α ˙" ˆ´? α ´2β α ˙3 ´α ˆ´? α ´2β α ˙`β " ´8 β 3 α 3 ´α3{2 ´6β ´12β 2 α 3{2 `α3{2 `3β " ´8β 3 α 3 ´12β 2 α 3{2 ´3β ă 0. Similarly, we have f ˆ?α ´2β α ˙" ´8β 3 α 3 `12β 2 α 3{2 ´3β " β ˆ´8β 2 α 3 `12β α 3{2 ´3˙ă ´8β 3 α 3 ă 0.

}a i } 2 ą 0, β i " ř j‰i xa i , a j y ζ 3 j }a i } 2 .

Then for any q P R C , we have

|β i | α 3{2 i " ˇˇř j‰i xa i , a j y ζ 3 j ˇˇ}ai} }ζ} 6 4 ď µM 3 }ζ} 3 3 }ζ} 6 4 ď M 3 ξ ´3{2 , (B.12)

where for the first inequality we used the fact that for any i P rms, }a i } ď M and ˇˇˇˇÿ

j‰i xa i , a j y ζ 3 j ˇˇˇˇď ˇˇˇˇÿ j‰i B a i }a i } , a j }a j } F ζ 3 j ˇˇˇˇ} a i } max 1ďjďm }a j } ď µM 2 m ÿ i"1 |ζ i | 3 " µM 2 }ζ} 3 3 ,

and the last inequality derives from the fact that q P R C . Thus, by Equation (B.5) and Equation (B.12), we obtain

M 3 ξ ´3{2 ď 1 4 ùñ |β i | α 3{2 i ď 1 4 .

This implies that the condition in Equation (B.9) holds, so that we can apply Lemma B.3 to characterize the critical points. Based on Lemma B.3, we classify critical points q P R C into three categories For Case 1, Lemma B.4 shows that this type of critical point does not exist under the assumption in Equation (B.5). For Case 2, under the same assumption, Lemma B.5 implies that such a critical point q P R C satisfies the second-order optimality condition, and it is near one of the target solution with

1. All |ζ i | (1 ď i ď m)

B a 1 }a 1 } , q F ě 1 ´5ξ ´3{2 M 3 ě 1 ´5η.

for some η ă 2 ´6. Finally, for Case 3, Lemma B.6 proves that this type of critical points q P R C is ridable saddle, for which the Riemannian Hessian exhibits negative eigenvalue. Therefore, the critical points in R C are either ridable saddle or near target solutions, so that there is no spurious local minimizer in R C .

In the following, we provided more detailed analysis for each case.

CASE 1: NO CRITICAL POINTS WITH SMALL ENTRIES.

First, we show by contradiction that if q P R C and is a critical points, then there is at least one coordinate, e.g., |ζ 1 | ě 2|β1| α1 . This implies that Case 1 (i.e., all |ζ i | (1 ď i ď m) are smaller than 2|βi| αi ) is impossible to happen. In other words, this means that any critical point q P R C should be close to superpositions of columns of A.

Lemma B.4 Suppose we have

M 4{3 K 1{3 ă 4 ´1{3 ξ.

If q P R C is a critical point, then there exists at least one i P rms such that the entry ζ i of ζpqq satisfies

|ζ i | ě 2 |β i | α i .

Proof Suppose there exists a q P R C such that all entries ζ i satisfying |ζ i | ă 2|βi| αi . Then we have

max 1ďiďm |ζ i | " }ζ} 8 ď 2 ˇˇř m k"2 xa 1 , a k y ζ 3 k ˇ}ζ} 4 4 ď 2M 2 µ }ζ} 3 3 }ζ} 4 4

. This implies that

}ζ} 4 4 ď }ζ} 2 8 }ζ} 2 ď 4M 4 µ 2 }ζ} 6 3 }ζ} 8 4 }ζ} 2 ùñ }ζ} 12 4 ď 4M 4 µ 2 }ζ} 6 3 }ζ} 2 ùñ }ζ} 4 4 ď 4 1{3 M 4{3 K 1{3 µ 2{3 }ζ} 2 3 ,

where we used the fact that }ζ} 2 " K according to Equation (B.1). Thus, by our assumption, we have

M 4{3 K 1{3 ă ξ{4 1{3 ùñ }ζ} 4 4 ă ξµ 2{3 }ζ} 2 3 .

This contradicts with the fact that q P R C . CASE 2: CRITICAL POINTS NEAR GLOBAL MINIMIZERS Second, we consider the case that there exists only one big ζ 1 , for which the critical point satisfies second-order optimality and is near a true component.

Lemma B.5 Suppose ξ is sufficiently large such that

M 3 ă η ¨ξ3{2 , KM ă 4 ´1 ¨ξ3{2 , (B.13)

for some constant η ă 2 ´6. For any critical point q P R C , if there is only one entry in ζ such that

ζ 1 ě 2|β1| α1 , B a 1 }a 1 } , q F ě 1 ´5ξ ´3{2 M 3 ě 1 ´5η.

Moreover, such a critical point q P R C satisfies the second-order optimality condition: for any

v P S n´1 with v K q, v J Hess ϕ T pqqv ě 1 20 }ζ} 4 4 .

Proof We first show that under our assumptions the critical point q P R C is near a target solution.

Following this, we prove that q also satisfies second-order optimality condition.

Closeness to target solutions. First, if q is a critical point such that there is only one ζ 1 ě 2|β1| α1 , we show that such q is very close to a true component. By Lemma B.2 and Lemma B.3, we know that ζ 1 needs to be upper bounded by

ζ 2 1 ď ˆ?α 1 `2 |β 1 | α 1 ˙2 " ˜}ζ} 2 4 }a 1 } `2 ˇˇř m k"2 xa 1 , a k y ζ 3 k ˇ}ζ} 4 4 ¸2 ď }ζ} 4 4 }a 1 } 2 ˜1 `2µ }ζ} 3 3 }a 1 } 2 max 1ďjďm }a j } }ζ} 6 4 ¸2 .

By using the fact that q P R C and }a j } ď M p1 ď j ď mq, we have

}a 1 } 2 ζ 2 1 ď ˜1 `2µ }ζ} 3 3 }a 1 } 2 max 1ďjďm }a j } }ζ} 6 4 ¸2 }ζ} 4 4 ď ´1 `2ξ ´3{2 M 3 ¯2 }ζ} 4 4 . (B.14)

On the other hand, by using the fact that

|ζ k | ď 2|β k | α k for all k ě 2, we have ζ 4 1 ě }ζ} 4 4 ´ζ2 2 m ÿ k"2 ζ 2 k ě }ζ} 4 4 ´4 |β 2 | 2 α 2 2 K ě }ζ} 4 4 ˜1 ´4µ 2 }ζ} 6 3 }ζ} 12 4 KM 4 ȩ }ζ} 4 4 `1 ´4ξ ´3K M 4 ˘. (B.15)

Combining the lower and upper bounds in Equation (B.14) and Equation (B.15), we obtain

B a 1 }a 1 } , q F 2 " ζ 2 1 }a 1 } 2 ě 1 ´4ξ ´3K M 4 `1 `2ξ ´3{2 M 3 ˘2 ě `1 ´4ξ ´3K M 4 1 `6ξ ´3{2 M 3 " 1 ´2ξ ´3M 3 ´3ξ 3{2 `2KM ě 1 ´8ξ ´3{2 M 3 ě 1 ´8η,

where the second inequality follows by Lemma A.2, and the last inequality follows from Equation (B.13). This further gives

B a 1 }a 1 } , q F ě 1 ´8ξ ´3{2 M 3 `1 ´8ξ ´3{2 M 3 ˘1{2 ě 1 ´8ξ ´3{2 M 3 1 ´4ξ ´3{2 M 3 " 1 ´5ξ ´3{2 M 3 ě 1 ´5η. (B.16)

Second-order optimality condition. Second, we check the second order optimality condition for the critical point. Let v P S n´1 be any vector such that v K q, then 

v J Hess ϕ T pqqv " ´3v J A diag `ζd2 ˘AJ v `}ζ} 4 4 " ´3 xa 1 , vy 2 ζ 2 1 ´3 m ÿ k"2 xa k , vy 2 ζ 2 k `}ζ} 4 4 ě ´3 xa 1 , vy 2 ζ 2 1 ´3ζ 2 2 › › A J v › › 2 `}ζ} 4 4 " ´3

xa 1 , vy 2 ¨ζ2 1 " B a 1 }a 1 } ´q, v F 2 ´}a 1 } 2 ζ 2 1 ď › › › › a 1 }a 1 } ´q› › › › 2 ´1 `2ξ ´3{2 M 3 ¯2 }ζ} 4 4 " 2 ˆ1 ´B a 1 }a 1 } , q F˙´1 `2ξ ´3{2 M 3 ¯2 }ζ} 4 4 ď 10ξ ´3{2 M 3 ´1 `2ξ ´3{2 M 3 ¯2 }ζ} 4 4 ď 1 4 }ζ} 4 4 . (B.18)

On the other hand, for q P R C , using Equation (B.13) we have Finally, we consider the critical points q P R C that at least two entries |ζ 1 | and |ζ 2 | are larger than 2|β1| α1 and 2|β2| α2 , respectively. For this type of critical points in R C , we show that they are ridable saddle points: the Hessian is nondegenerate and exhibits negative eigenvalues.

Kζ 2 2 ď K 4 |β 2 | 2 α 2 2 ď 4KM 4 µ

Lemma B.6 Suppose we have

M 3 ă η ¨ξ3{2 , µ ă 1 20 , (B.20)

for some constant η ă 2 ´6 For any critical point q P R C , if there are at least two entries in ζpqq such that |ζ i | ą 2|βi| αi pi P rmsq, then q is a strict saddle point: there exists some v P S n´1 with v K q, such that

v J Hess ϕ T pqqv ď ´}ζ} 4 4 .

Proof Without loss of generality, for any critical point q P R C , we assume that ζ 1 " a J 1 q and ζ 2 " a J 2 q are the two largest entries in ζpqq. We pick a vector v P span

EQUATION

) such that v K q with v P S n´1 . Thus,

v J Hess ϕ T pqqv " ´3v J A diag `ζd2 ˘AJ v `}ζ} 4 4 ď ´3 }a 1 } 2 ζ 2 1 B a 1 }a 1 } , v F 2 ´3 }a 2 } 2 ζ 2 2 B a 2 }a 2 } , v F 2 `}ζ} 4 4 . Since |ζ 1 | ě 2|β1| α1 and |ζ 2 | ě 2|β2| α2 , by Lemma B.2, Lemma B.

3, and the fact that q P R C , we have

}a 1 } 2 ζ 2 1 ě }a 1 } 2 ˆ?α 1 ´2 |β 1 | α 1 ˙2 ě ˜1 ´2µM 2 }ζ} 3 3 }a 1 } }ζ} 6 4 ¸2 }ζ} 4 4 ě ´1 ´2ξ ´3{2 M 3 ¯2 }ζ} 4 4 .

In the same vein, we can also show that

}a 2 } 2 ζ 2 2 ě ´1 ´2ξ ´3{2 M 3 ¯2 }ζ} 4 4

. Therefore, combining the results above, we obtain

EQUATION

) , we can write

v " c 1 a 1 }a 1 } `c2 a 2 }a 2 }

for some coefficients c 1 , c 2 P R. As v P S n´1 , we observe

}v} 2 " c 2 1 `c2 2 `2c 1 c 2 B a 1 }a 1 } , a 2 }a 2 } F " 1 ùñ c 2 1 `c2 2 ě 1 ´2 |c 1 c 2 | µ ě 1 ´4µ,

where the last inequality follows from Lemma B.7. Thus, we observe

B a 1 }a 1 } , v F 2 `B a 2 }a 2 } , v F 2 " ˆc1 `c2 B a 1 }a 1 } , a 2 }a 2 } F˙2 `ˆc 2 `c1 B a 1 }a 1 } , a 2 }a 2 } F˙2 " `c2 1 `c2 2 ˘``c 2 1 `c2 2 ˘B a 1 }a 1 } , a 2 }a 2 } F 2 `4c 1 c 2 B a 1 }a 1 } , a 2 }a 2 } F ě 1 ´4µ ´p1 ´4µq µ 2 ´4 1 `µ 1 ´µ2 µ ě 1 ´10µ

By the fact in Equation (B.20) and combining all the bounds above we obtain

v J Hess ϕ T pqqv ď " 1 ´3 ´1 ´2ξ ´3{2 M 3 ¯2 p1 ´10µq  }ζ} 4 4 ď ´1 4 }ζ} 4 4 .

This completes the proof.

EQUATION

EQUATION

}a2} , then we have

EQUATION

Eˇˇˇď 1, we have

ˇˇˇˆc 1 `c2 B a 1 }a 1 } , a 2 }a 2 } F˙ˆc 2 `c1 B a 1 }a 1 } , a 2 }a 2 } F˙ˇˇˇˇď 1,

which further implies that

ˇˇˇˇc 1 c 2 ``c 2 1 `c2 2 ˘B a 1 }a 1 } , a 2 }a 2 } F `c1 c 2 B a 1 }a 1 } , a 2 }a 2 } F 2 ˇˇˇˇď 1.

Since }v} " 1, we also have

c 2 1 `c2 2 " 1 ´2c 1 c 2 B a 1 }a 1 } , a 2 }a 2 } F .

Combining the two (in)equalities above, we obtain

1 ě ˇˇˇˇc 1 c 2 `B a 1 }a 1 } , a 2 }a 2 } F ´c1 c 2 B a 1 }a 1 } , a 2 }a 2 } F 2 ˇˇˇě |c 1 c 2 | ˜1 ´B a 1 }a 1 } , a 2 }a 2 } F 2 ¸´ˇˇˇˇB a 1 }a 1 } , a 2 }a 2 } Fˇˇˇˇě |c 1 c 2 | `1 ´µ2 ˘´µ.

Thus, we obtain the desired result.

B.2 NEGATIVE CURVATURE IN R N:

Finally, we make more stringent assumption on A that each column of A is 2 normalized, i.e.,

}a i } " 1, 1 ď i ď m.

We show that the function ϕ T pqq exhibits negative curvature in the region R N . Namely, the Riemannian Hessian for any points q P R N has a negative eigenvalue, such that the Hessian is negative in a certain direction.

Lemma B.8 Suppose each column of A is 2 normalized and

K ď 3 ´1 `6µ `6ξ 3{5 µ 2{5 ¯´1 .

For any point q P R N , there exists some direction d P S n´1 , such that

d J Hess ϕ T pqqd ă ´4 }ζ} 4 4 }ζ} 2 8 .

Proof By definition, we have `Kw here for the second inequality we used the fact that }ζ} 4 4 ď }ζ} 2 8 }ζ} 2 , and for the last equality we applied that }ζ} 2 " q J AA J q " K. Moreover, as q P R N , we have

a J 1 Hess ϕ T pqqa 1 " ´3a J 1 P q K A diag `ζd2 ˘A˚P q K a 1 `}ζ} 4 4 › › P q K a 1 › › 2 " ´3a J 1 A diag `ζd2 ˘AJ a 1 `6 }ζ} 8 ζ J diag `ζd2 ˘AJ a 1 ´3

}ζ} 2 8 ď }ζ} 2 4 ď ξ 1{2 µ 1{3 }ζ} 3 }ζ} 3 " ˜m ÿ k"1 |ζ k | 3 ¸1{3 ď }ζ} 1{3 8 K 1{3 .

Thus, we obtain

}ζ} 2 8 ď ξ 1{2 µ 1{3 }ζ} 1{3 8 K 1{3 ùñ }ζ} 2 8 ď ξ 3{5 pµKq 2{5 .

Hence, we have

a J 1 Hess ϕ T pqqa 1 ď }ζ} 2 8 ´´3 `6ξ 3{5 pµKq 2{5 `6µK ´4 }ζ} 4 4 `K¯ď ´4 }ζ} 4 4 }ζ} 2 8 , whenever K ď 3 ´1 `6µ `6ξ 3{5 µ 2{5 ¯´1

.

Thus, we obtain the desired result.

C OPTIMIZATION LANDSCAPE IN FINITE SAMPLE:

In this section, we will show that the finite sample objective functions in the overcomplete dictionary learning and convolutional dictionary learning have similar geometric properties as

ϕ T pqq " ´1 4 › › A J q › › 4 4 analyzed in Appendix B

. Specifically, we will analyze the geometric properties of objective function ϕpqq (which could be ϕ DL pqq and ϕ CDL pqq) whose gradient and Hessian are close to ϕ T pqq. We denote by δ g pqq :" grad ϕpqq ´grad ϕ T pqq, ∆ H pqq :" Hess ϕpqq ´Hess ϕ T pqq, (C.1) both of which will be proved to be small for overcomplete dictionary learning and convolutional dictionary learning in Appendix F. Also suppose we have

KM ă 8 ´1 ¨ξ3{2 , M 3 ă 2η ¨ξ3{2 , µ ă 1 20 (C.2)

for some constant η ă 2 ´6. Then any critical point q P R C , with grad ϕpqq " 0, either is a ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components e.g., a 1 in the sense that

B a 1 }a 1 } , q F ě 1 ´5ξ ´3{2 M 3 ě 1 ´5η. (C.3)

Proof [Proof of Proposition C.1] With the same argument in Lemma B.2, we have that any critical point q P S n´1 satisfies f pζ i q " ζ 3 i ´αi ζ i `β1 i " 0, for all i P rms with ζ " A J q, where α i " }ζ}

4 4 }a i } 2 , β 1 i " xδ g pqq, a i y `řj‰i xa i , a j y ζ 3 j }a i } 2 " β i `xδ g pqq, a i y }a i } 2 , (C.4) with β i " ř j‰i xai,aj yζ 3 j }ai} 2

which is defined in equation B.7.

Recall that a widely used upper bound for β i in Appendix B.1 is:

|β i | " ˇˇř j‰i xa i , a j y ζ 3 j ˇ} a i } 2 ď µM }ζ} 3 3 }a i } ,

which together with }δ g pqq} ď µM }ζ}

3 3 gives β 1 " β i `xδ g pqq, a i y }a i } 2 ď 2 µM }ζ} 3 3 }a i } . (C.5)

To easily utilize the proofs in Appendix B.1, we define ξ 1 " 2 ´2{3 ξ such that ξ 1´3{2 " 2ξ ´3{2 .

Plugging the assumption M 3 ξ 1´3{2 ď 1 4 into equation C.5, we have

|β 1 i | α 3{2 i ď 2 µM }ζ} 3 3 }a i } 2 }ζ} 6 4 ď 2 µM 3 }ζ} 3 3 }ζ} 6 4 ď 2M 3 ξ ´3{2 ď 2M 3 ξ 1´3{2 ď 1 4 .

This implies that the condition in equation B.9 holds, so that we can apply Lemma B.3 based on which we classify critical points q P R C into three categories 1. All |ζ i | (1 ď i ď m) are smaller than

2|β 1 i | αi ; 2. Only |ζ 1 | is larger than 2|β 1 1 | α1 ; 3. At least |ζ 1 | and |ζ 2 | are larger than 2|β 1 1 | α1 and 2|β 1 2 | α2 , respectively.

For Case 1, using the same argument as in Lemma B.4 we can easily show that this type of critical point does not exist. For Case 2, with the same argument as in Lemma B.5, we obtain that such a critical point is near one of the target solution with

B a 1 }a 1 } , q F ě 1 ´5ξ 1´3{2 M 3 ě 1 ´5η,

and satisfies the second-order optimality condition, i.e., for any v P S n´1 with v K q, we have

v J Hess ϕpqqv ě v J Hess ϕ T pqqv ´}∆ H pqq} ě 1 20 }ζ} 4 4 ´}∆ H pqq} .

Finally, for Case 3, with the same v constructed in Lemma B.6 and using the assumption }∆ H pqq} ă . Also suppose each column of A is 2 normalized and

K ď 3 ´1 `6µ `6ξ 3{5 µ 2{5 ¯´1

.

For any point q P R N , there exists some direction d P S n´1 , such that

d J Hess ϕpqqd ă ´3 }ζ} 4 4 }ζ} 2 8 .

Proof First, it follows Lemma B.8 that for any point q P R N , there exists some direction d P S n´1 , such that d J Hess ϕ T pqqd ă ´4 }ζ} 

D OVERCOMPLETE DICTIONARY LEARNING:

In this section, we consider the nonconvex problem of

min q ϕ DL pqq " ´1 12θp1 ´θqp › › q J Y › › 4 4 " ´1 12θp1 ´θqp › › q J AX › › 4 4 , s.t.

}q} " 1. We characterize its expectation and optimization landscape as follows.

D.1 EXPECTATION CASE: OVERCOMPLETE TENSOR DECOMPOSITION:

First, we show that ϕ DL pqq reduces to ϕ T pqq in expectation w.r.t. X. Lemma D.1 When X is i.i.d. drawn from Bernoulli Gaussian distribution as in Assumption 2.2, then we have

E X rϕ DL pqqs " ϕ T pqq ´θ 2p1 ´θq ´m n ¯2 .

Proof Let ζ " A J q P R m with }ζ} 2 " m n . By using the fact that ˘. Also suppose we have

EQUATION

K ă max " 8 ´1 ¨ξ3{2 , 3 ´1 `6µ `6ξ 3{5 µ 2{5 ¯´1 * , 1 ă 2η ¨ξ3{2 , µ ă 1 20

for some constant η ă 2 ´6.

• If p ě CθK 3 n 3 max ! logpθn 7{2 {µq µ 2

, Kn 2 logpθn 2 q ) , then with probability at least 1 ´cp ´2, any critical point q P R C of ϕ DL pqq either is a ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components e.g., a 1 in the sense that

B a 1 }a 1 } , q F ě 1 ´5ξ ´3{2 M 3 ě 1 ´5η.

• If p ě CθK 4 n 6 logpθn 5 q, then with probability at least 1 ´cp ´2, any critical point q P R N of ϕ DL pqq is a ridable (strict) saddle point.

Here, c, C ą 0 are some numerical constants.

Proof First note that for overcomplete dictionary A in Equation (2.2), it satisfies Equation (F.9) with M " 1. Now it follows from Proposition F. which together with Proposition C.1 implies that any critical point q P R C of ϕ DL pqq either is a ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components e.g., a 1 in the sense that

B a 1 }a 1 } , q F ě 1 ´5η.

We complete the proof for q P R C by plugging inequalities 

}ζ} 3 ě m ´1{6 }ζ} 2 " K 1{3 n ´1{6 and }ζ} 4 ě m ´1{4 }ζ} 2 " K 1{4 n ´1{4 into

E CONVOLUTIONAL DICTIONARY LEARNING:

In this part of appendix, we provide the detailed analysis for CDL. Recall from Section 3, we denote

Y " " C y1 C y2 ¨¨¨C yp ‰ P R nˆp , A 0 " rC a1 C a2 ¨¨¨C a K s P R nˆm , x i " » - - - x i1 x i2 . . . x iK fi ffi ffi fl P R m , X i " » - - - C xi1 C xi2 . . . C x iK fi ffi ffi fl P R mˆn , X " rX 1 X 2 ¨¨¨X p s P R nˆnp ,

For simplicity we let

A " `K´1 A 0 A J 0 ˘´1{2 A 0 , m " nK.

Recall from Section 3, for CDL we make the following assumptions on A 0 , A and X.

Assumption E.1 (Properties of A 0 and A) We assume the matrix A 0 has full row rank with minimum singular value: σ min pA 0 q ą 0, condition number: κpA 0 q :" σ max pA 0 q σ min pA 0 q .

In addition, we assume the columns of A are mutually incoherent in the sense that

max i "j ˇˇˇB a i }a i } , a j }a j } Fˇˇˇˇď µ. Assumption E.2 (Bernoulli-Gaussian x ik ) We assume entries of x ik " i.i.d. BGpθq that x ik " b ik d g ik , b ik " i.i.d. Berpθq, g ik " i.i.d. N p0, Iq, 1 ď i ď p, 1 ď k ď K.

In comparison with Assumption 2.1, it should be noted that the preconditioning does not necessarily result in 2 -normalized columns of A. But their norms are still bounded in the sense that

}a k } 2 ď › › A J a k › › ď ? K }a k } ùñ }a k } ď ? K, 1 ď k ď nK.

(E.1) Because of the unbalanced columns of A, unlike the ODL problem, the CDL problem

min qPS n´1 ϕ CDL pqq " ´1 12θp1 ´θqnp › › q J P Y › › 4 4 " ´1 12θp1 ´θqp › › q J P A 0 X › › 4 4

does not have global geometric structures in the worst case. But still we can show that the problem is benign in local regions in the following. Moreover, we also show that we can cook up data driven initialization which falls into the local region.

E.1 MAIN RESULT OF OPTIMIZATION LANDSCAPE:

In this part, we show our main result for optimization landscape for CDL. Namely, consider the region introduced in Equation (3.3) as R CDL :"

! q P S n´1 ˇˇϕ T pqq ď ´ξCDL κ 4{3 µ 2{3 }ζpqq} 2 3

) ,

where ξ CDL ą 0 is a fixed numerical constant. We show the following result.

Theorem E.3 (Local geometry of nonconvex landscape for CDL) Let C 0 ą 5 be some constant and η ă 2 ´6. Suppose we have

θ P ˆ1 nK , 1 3 ˙, ξ CDL " C 0 ¨η´2{3 K, µ ă 1 40 , K ă C 0 ,

and we assume Assumption E.1 and Assumption E.2 hold. There exists some constant C ą 0, with probability at least 1 ´c1 pnKq ´c2 over the randomness of x ik s, whenever p ě CθK 2 µ ´2n 4 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q

, n * log 6 pm{µq, every critical point q c of ϕ CDL pqq in R CDL is either a strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a 1 ) such that

B a 1 }a 1 } , q c F ě 1 ´5κ ´2η.

Proof Noting Equation (E.1), we set M " ? K in Proposition C.1. It follows from Proposition E.11 that when p ě CθK 4 n 2 log 5 pmKq max Thus, by using Proposition C.1, we have that any critical point q c P R CDL of ϕ CDL pqq either is a ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components, e.g., a 1 in the sense that

" K 6 κ 6 pA 0 q σ 2 min pA 0 q , n * ¨max # logpθKn{µK 1{2 }ζ} 3 3 q µ 2 K }ζ}

B a 1 }a 1 } , q c F ě 1 ´5ξ ´3{2 CDL K 3{2 κ ´2 ě 1 ´5ηκ ´2,

where we have plugged M " ? K and ξ " ξ CDL κ 4{3 in Equation (C.3). Finally, we complete the proof by using inequalities }ζ} 3 ě m ´1{6 }ζ} 2 " K 1{3 n ´1{6 and }ζ} 4 ě m ´1{4 }ζ} 2 " K 1{4 n ´1{4 in Equation (E.2).

E.2 PROOF OF OPTIMIZATION:

In the following, we show that with high probability Algorithm 1 with initialization returns an approximate solution of one of the kernels up to a shift.

Proposition E.4 (Global convergence of Algorithm 1) With m " nK, suppose c 1 log m m ď θ ď c 2 µ ´2{3 κ 4{3 m log m ¨min " κ 4{3 µ 4{3 , Kµ ´4 m 2 log m * . (E.3) Whenever p ě CθK 2 µ ´2 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q

, n * n 4 log 6 pm{µq , our initialization in Algorithm 1 satisfies

q init P R CDL :" ! q P S n´1 | ϕ T pqq ď ´ξCDL µ 2{3 κ 4{3 K ) Ă R CDL , (E.4)

such that all future iterates of Algorithm 1 stays within R CDL and converge to an approximate solution (e.g., a circulant shift s ra 01 s of a 01 ) in the sense that › › P S n´1 `P ´1q ‹ ˘´s ra 01 s › › ď , where is a small numerical constant.

Proof Note that R CDL Ď R CDL is due to the fact that › › A J q › › 2 3 ď › › A J q › › 2 " K.

We show that the iterates of Algorithm 1 converge to one of the target solutions by the following.

Initialization falls into R CDL . From Proposition E.5, taking ξ " ξ CDL κ 4{3 , with θ satisfies Equation (E.3), whenever

p ě C 1 K 2 µ 4{3 θ κ 10{3 pA 0 q σ 2 min pA 0 q logpmq,

w.h.p. our initialization q init satisfies ϕ T pq init q ď ´2ξ CDL µ 2{3 κ 4{3 K.

Iterate stays within the region. Let tq pkq u be the sequence generated by Algorithm 1 with q p0q " q init . From Proposition E.12, we know that whenever

p ě C 2 θK 2 µ 4{3 κ 8{3 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q , n * n 2 log ´θnµ ´2{3 κ ´4{3 ¯log 5 pmKq,

we have

sup qPS n´1 ˇˇˇϕ CDL pqq ´ˆϕ T pqq ´θ 2p1 ´θq K 2 ˙ˇˇˇď 1 2 ξ CDL µ 2{3 κ 4{3 K,

which together with the fact that the sequence tq pkq u satisfies ϕ CDL pq pkq q ď ϕ CDL pq p0q q implies ϕ T pq pkq q ď ϕ CDL pq pkq q `θ 2p1 ´θq

K 2 `1 2 ξ CDL µ 2{3 κ 4{3 K ď ϕ CDL pq p0q q `θ 2p1 ´θq K 2 `1 2 ξ CDL µ 2{3 κ 4{3 K ď ϕ T pq p0q q `ξCDL µ 2{3 κ 4{3 K ď ´ξCDL µ 2{3 κ 4{3 K.

Closeness to the target solution. From Theorem E.3, we know that whenever p ě CθK 2 µ ´2n 4 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q

, n * log 6 pm{µq, the function ϕ CDL pqq has benign optimization landscape, that whenever our method can efficient escape strict saddle points, Algorithm 1 produces a solution q ‹ that is close to one of the target solutions (e.g. a 1 , the first column of A) in the sense that

B a 1 }a 1 } , q ‹ F ě 1 ´ε, with ε " κ ´2η.

In the following, we show that our final output a ‹ " P S n´1 `P ´1q ‹ ˘should be correspondingly close to a circulant shift of one of the kernels ta 0k u K k"1 . Without loss of generality, suppose q ‹ " a 1 , then the corresponding solution should be a 01 with zero shift (or in other words, the first column a 01 of A 0 ). In the following, we make this rigorous. Notice that

› › P S n´1 `P ´1q ‹ ˘´a 01 › › " › › › › P S n´1 `P ´1q ‹ ˘´P S n´1 ˆa01 }a 1 } ˙› › › › ď 2 }a 1 } › › › › P ´1q ‹ ´a01 }a 1 } › › › ›

, where for the last inequality we used Lemma A.12. Next, by triangle inequality, we have

› › P S n´1 `P ´1q ‹ ˘´a 01 › › ď 2 }a 1 } › › › › P ´1 a 1 }a 1 } ´a01 }a 1 } › › › › `2 }a 1 } › › › › P ´1 ˆa1 }a 1 } ´q‹ ˙› › › › " 2 › › › ´P ´1 `K´1 A 0 A J 0 ˘´1{2 ´I¯a 01 › › › `2 }a 1 } › › › › P ´1 ˆa1 }a 1 } ´q‹ ˙› › › › ď 2 › › › › › ˆ1 θmp Y Y J ˙1{2 `A0 A J 0 ˘´1{2 ´I› › › › › `2? 2 }a 1 } › › P ´1› › d 1 ´B a 1 }a 1 } , q ‹ F .

Let δ P p0, 1q be a small constant. From Lemma E.18 and Corollary E.19, we know that whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q δ ´2 logpmq,

we have › › › › › ˆ1 θmp Y Y J ˙1{2 `A0 A J 0 ˘´1{2 ´I› › › › › ď δ, › › P ´1› › ď 2K ´1{2 }A 0 } .

Therefore, we obtain

› › P S n´1 `P ´1q ‹ ˘´a 01 › › ď 2δ `4? 2 }A 0 } ? ε ď 2δ `4? 2 ? ησ max pA 0 qκ ´1 ď 2δ `4? 2 ? η ď

when η is sufficiently small. Here, is a small numerical constant.

E.3 PROOF OF INITIALIZATION:

In this subsection, we show that we can cook up a good data-driven initialization. We initialize the problem by using a random sample (1 ď ď p) q init " P S n´1 pP y q , 1 ď ď p, which roughly equals to q init « P S n´1 pAx q , A J q init « ? KP S m´1 `AJ Ax ˘.

For generic kernels, A J A is a close to a diagonal matrix, as the magnitudes of off-diagonal entries are bounded by column mutual incoherence. Hence, the sparse property of x should be approximately preserved, so that A J q init is spiky with large › › A J q init › › 4 4 . We define

ζ init " A J q init , p ζ init " ? KP S m´1 `AJ Ax ˘.

By leveraging the sparsity level θ, one can make sure that such an initialization q init suffices.

Proposition E.5 Let m " nK. Suppose the sparsity level θ satisfies

c 1 log m m ď θ ď c 2 Kµ ´2{3 ξm log m ¨min " ξ Kµ 4{3 , µ ´4 m 2 log m * . Whenever p ě C K 2 µ 4{3 ξ 2 θ κ 6 pA 0 q σ 2 min pA 0 q logpmq,

for some ξ ą 0 we have

}ζ init } 4 4 ě ξKµ 2{3

holds with probability at least 1 ´cm ´c1 . Here, c 1 , c 2 , c, c 1 , C ą 0 are some numerical constants.

Proof By using the convexity of 4 -loss, we can show that the values of }ζ init } 4 4 and

› › › p ζ init › › › 4 4 are close, }ζ init } 4 4 ě › › › p ζ init › › › 4 4 `4 A p ζ d3 init , ζ init ´p ζ init E ě › › › p ζ init › › › 4 4 ´4 › › › p ζ d3 init › › › › › ›ζinit ´p ζ init › › › ě › › › p ζ init › › › 4 4 ´4K 3{2 › › ›ζinit ´p ζ init › › › loooooomoooooon small . (E.5)

Thus, it is enough to lower bound

› › › p ζ init › › › 4 4

. Let I " supppx q, and let P I : R m Þ Ñ R m that maps all off support entries to zero and all on support entries to themselves. Thus, we have

› › › p ζ init › › › 4 4 " K 2 › › A J Ax › › ´4 › › A J Ax › › 4 4 ě K 2 ´› › P I `AJ Ax ˘› › 2 `› › P I c `AJ Ax ˘› › 2 ¯´2 › › P I `AJ Ax ˘› › 4 4 " K 2 p1 `ρq 2 › › P S n´1 `PI `AJ Ax ˘˘› › 4 4 ,

with ρ :" ˆ}P I c pA J Ax q} }PI pA J Ax q} ˙2. By Lemma E.7 and Lemma E.9, whenever

c 1 log m m ď θ ď c 2 µ ´2 m log m ,

we have

› › P I c `AJ Ax ˘› › ď C 1 Kµm a θ log m, › › P I `AJ Ax ˘› › ě 1 ? 2 K ? θm

holding with probability at least 1 ´c3 m ´c4 , so that

ρ " ˜› › P I c `AJ Ax ˘› › }P I pA J Ax q} ¸2 ď C 2 µ 2 m log m.

Thus, we have

› › › p ζ init › › › 4 4 ě K 2 p1 `ρq ´2 › › P S m´1 `PI A J Ax ˘› › 4 4 ě C 3 K 2 µ 4 m 2 log 2 m › › P S m´1 `PI A J Ax ˘› › 4 4 .

By Lemma E.10, we have

› › P S m´1 `PI A J Ax ˘› › 4 4 ě 1 2θm

with probability at least 1 ´c5 m ´c6 . Thus, with high probability, we have

› › › p ζ init › › › 4 4 ě C 3 K 2 µ 4 m 2 log 2 m ¨1 2θm ě 2ξKµ 2{3 , (E.6) whenever θ ď C 4 Kµ ´2{3 ξm ¨1 µ 4 m 2 log 2 m .

Finally, Lemma E.6 implies that for any δ P p0, 1q, whenever

p ě C 5 θ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q δ ´2 logpmq, it holds that › › ›ζinit ´p ζ init › › › ď δ,

with probability at least 1 ´c7 pmq ´c8 . Choose δ such that

4K 3{2 › › ›ζinit ´p ζ init › › › ď 4K 3{2 δ ď ξKµ 2{3 ùñ δ ď C 6 ξK ´1{2 µ 2{3 , (E.7)

then by Equations (E.5) to (E.7) we have

}ζ init } 4 4 ě › › › p ζ init › › › 4 4 ´4K 3{2 › › ›ζinit ´p ζ init › › › ě ξKµ 2{3 .

Summarizing all the result above, we obtain the desired result.

Lemma E.6 Let δ P p0, 1q. Whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q δ ´2 logpmq, we have

› › ›ζinit ´p ζ init › › › ď δ

with probability at least 1 ´c1 pKnq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof By definition, we observe

› › ›ζinit ´p ζ init › › › " › › ›A J P S n´1 pP y q ´?KP S n´1 `AJ Ax ˘› › › " › › › › › A J P S n´1 ˜ˆ1 θKmp Y Y J ˙´1{2 A 0 x ¸´? KP S n´1 `AJ Ax ˘› › › › › " › › › › › › › › A J ´1 θmp Y Y J ¯´1{2 A 0 x › › › › ´1 θmp Y Y J ¯´1{2 A 0 x › › › › ´AJ Ax }Ax } › › › › › › › › ď 2 }A} }Ax } › › › › › ˆ1 θmp Y Y J ˙´1{2 A 0 x ´`A 0 A J 0 ˘´1{2 A 0 x › › › › › ď 2 ? K }x } }Ax } }A 0 } › › › › › ˆ1 θmp Y Y J ˙´1{2 ´`A 0 A J 0 ˘´1{2 › › › › › " 2 ? K }A 0 } › › › › › ˆ1 θmp Y Y J ˙´1{2 ´`A 0 A J 0 ˘´1{2 › › › › ›

, where for the first inequality we invoked Lemma A.12, and the last equality follows the fact that minimum singular value of A is unity. Next, by Lemma E.18, for some P p0, 1q, whenever

p ě Cθ ´1K 2 κ 4 pA 0 q σ 4 min pA 0 q ´2 logpmq, we have › › ›ζinit ´p ζ init › › › ď 8 ? K }A 0 }

holding with probability at least 1 ´c1 pmq ´c2 . Here, c 1 , , c 2 , C ą 0 are some numerical constants. Replace δ " 8 ? K }A 0 } , we obtain the desired result.

Lemma E.7 Suppose the columns of A are µ-incoherent and satisfies Assumption 3.1, and suppose x satisfies Assumption E.2. Let I " supp px q. For any t ě 0, we have

› › P I c `AJ Ax ˘› › ď › › offdiag `AJ A ˘x › › ď t

holds with probability at least 1 ´4m exp ´´min

! t 2 4K 2 µ 2 θm 2 , t 4Kµm ? m

)¯.

Proof Since we have

› › P I c `AJ Ax ˘› › ď › › offdiag `AJ A ˘x › › , (E.8) we could bound › › P I c A J Ax › › via controlling › › offdiag `AJ A ˘x › › . Let M " offdiag `AJ A ˘" rm 1 ¨¨¨m m s P R mˆm , and s " M x " m ÿ k"1 m k x k loomoon s k .

Thus, we can apply vector version Bernstein inequality. By Lemma A.3 and the fact that

}m k } ď Kµ ? m, E rs k s " 0, E r}s k } p s " θ }m k } p E g"N p0,1q r|g| p s ď m! 2 θ `Kµ ? m ˘p .

Therefore, by applying Lemma A.6, we obtain

P `› › offdiag `AJ A ˘x › › ě t ˘" P ˜› › › › › m ÿ k"1 s k ´E rss › › › › › ě t ḑ 2pm `1q exp ˆ´t 2 2µ 2 K 2 θm 2 `2Kµm ? mt ˙.

Finally, Equation (E.8) gives the desired result.

Lemma E.8 We have

› › diag `AJ A ˘x › › 2 ď K 2 θm (E.9)

with probability at least 1 ´exp ´´1 min

! t 2 K 4 θm , t K 2 m )¯. Proof First, let d " diag `AJ A ˘, s " › › diag `AJ A ˘x › › 2 " m ÿ k"1 d 2 k x 2 k lo omo on s k

, where by Lemma A.4, we have

E r|s k | p s ď θK 2p p!2 p 2 , E rss " θ › › diag `AJ A ˘› › 2 F ă K 2 θm.

Thus, by Bernstein inequality in Lemma A.5, we obtain

P ´› › diag `AJ A ˘x › › 2 ´K2 θm ě t ¯ď exp ˆ´t 2 4K 4 θm `4K 2 mt ˙,

as desired.

Lemma E.9 Suppose x satisfies Assumption E.2. Suppose x satisfies Assumption E.2. Let I " supp px q. Whenever θ satisfies

c 1 log m m ď θ ď c 2 µ ´2 m log m , (E.10)

we have

› › P I `AJ Ax ˘› › 2 ě 1 2 K 2 θm (E.11)

with probability at least 1 ´m´c . Here, c, c 1 , c 2 ą 0 are some numerical constants.

Proof Notice that

› › P I `AJ Ax ˘› › 2 " › › diag `AJ A ˘x `PI `offdiag `AJ A ˘x ˘› › 2 " › › diag `AJ A ˘x › › 2 `› › P I `offdiag `AJ A ˘x ˘› › 2 `2 @ diag `AJ A ˘x , P I `offdiag `AJ A ˘x ˘D ě › › diag `AJ A ˘x › › 2 ´2 › › diag `AJ A ˘x › › › › P I `offdiag `AJ A ˘x ˘› › .

By Lemma A.9, Lemma E.7, and Lemma E.8, we have

› › diag `AJ A ˘x › › 2 ď K 2 θm `C1 K 2 a θm log m › › P I `offdiag `AJ A ˘x ˘› › ď C 2 θKµm a log m

holds with probability at least 1 ´m´c0 . Thus, we obtain

› › P I `AJ Ax ˘› › 2 ě K 2 θm ˜1 ´C1 c log m θm ´C3 µ a θm log m ¸.

Finally, by using Equation (E.10), we have holds with probability at least 1 ´m´c .

› › P I `AJ Ax ˘› › 2 ě 1 2 K 2 θm

E.4 CONCENTRATION AND PERTURBATION:

We prove the following concentration results for Riemannian gradient and Hessian, and its function value.

Proposition E.11 For some small δ P p0, 1q, whenever the sample complexity satisfies

p ě Cδ ´2θK 4 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q , n * n 2 log ˆθKn δ ˙log 5 pmKq,

we have

sup qPS n´1 }grad ϕ CDL pqq ´grad ϕ T pqq} ď δ sup qPS n´1

}Hess ϕ CDL pqq ´Hess ϕ T pqq} ď δ hold with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof Let p ϕ CDL pqq be introduced as Equation (E.12) }grad p ϕ CDL pqq ´grad ϕ T pqq} .

EQUATION

From Proposition E.13, we know that whenever p ě C 1 θK 10 κ 6 pA 0 q σ 2 min pA 0 q δ ´2n 2 log 5 pmKq, }Hess p ϕ CDL pqq ´Hess ϕ T pqq} .

From Proposition E.15, we know that whenever p ě C 3 θK 10 κ 6 pA 0 q σ 2 min pA 0 q δ ´2n 2 log 5 pmKq, we have

sup qPS n´1

}Hess ϕ CDL pqq ´Hess p ϕ CDL pqq} ď δ 2

with probability at least 1 ´c4 pmKq ´c5 . On the other hand, Corollary F.10 implies that whenever p ě C 4 θK 6 δ ´2n 3 log pθKn{δq , we have

sup qPS n´1 }Hess ϕ DL pqq ´Hess ϕ T pqq} ă δ 2

holds with probability at least 1 ´c4 np ´2. Combining the bounds above gives the desired result on the Hessian.

Similar to Lemma D.1, for convolutional dictionary learning, asymptotically we have

E X rϕ CDL pqqs « E X r p ϕ CDL pqqs " ϕ T pqq ´θ 2p1 ´θq K 2 , ϕ T pqq " ´1 4 › › q J A › › 4 4 .

Next, we turn this asymptotical results into finite sample for the function value via concentration and preconditioning.

Proposition E.12 For some small δ P p0, 1q, whenever the sample complexity satisfies

p ě Cδ ´2θK 4 max " K 6 κ 6 pA 0 q σ 2 min pA 0 q , n * n 2 log ˆθKn δ ˙log 5 pmKq,

we have .

sup qPS n´1 › › › › ϕ CDL pqq ´ˆϕ T pqq ´θ 2p1 ´θq K 2 ˙› › › › ď

Thus, by using Corollary E.14 we can control T 1 . For T 2 , we can control in a similar way as Corollary F.9 or Corollary F.10. For simplicity, we omitted here.

Published as a conference paper at ICLR 2020

E.5 PRECONDITIONING:

In this part of appendix, let us introduce

ϕ CDL pqq " ´1 12θp1 ´θqnp › q J pP A 0 qX › › , p ϕ CDL pqq ´1 12θp1 ´θqnp › › q J AX › › . (E.12)

In the following, we show that the differences of function value, Riemannian gradient, and Hessian of those two functions are small by preconditioning analysis. For simplicity, let us also introduce v 0 pqq " X J pP A 0 q J q, vpqq " X J A J q.

(E.13)

E.5.1 CONCENTRATION AND PRECONDITIONING FOR RIEMANNIAN GRADIENT AND FUNCTION VALUE:

First, the gradients of ϕ CDL pqq and p ϕ CDL pqq and their Riemannian variants can be written as

∇ϕ CDL pqq " ´1 3θp1 ´θqnp P A 0 Xv d3 0 , ∇ p ϕ CDL pqq " ´1 3θp1 ´θqnp AXv d3 , grad ϕ CDL pqq " P q K ∇ϕ CDL pqq, grad p ϕ CDL pqq " P q K ∇ p ϕ CDL pqq,

where recall from Section 3 that we introduced the following preconditioning matrix

P " ˆ1 θKmp Y Y J ˙´1{2 " « A 0 ˜1 θKmp p ÿ i"1 X i X J i ¸AJ 0 ff ´1{2 .

In the following, we show that the difference between grad ϕ CDL pqq and grad p ϕ CDL pqq is small.

Proposition E.13 Suppose θ P `1 m , 1 2 ˘. For any δ P p0, 1q, whenever p ě CθK 10 κ 6 pA 0 q σ 2 min pA 0 q δ ´2n 2 log 5 pmKq, we have

sup qPS n´1 }grad ϕ CDL pqq ´grad p ϕ CDL pqq} ď δ sup qPS n´1

}∇ϕ CDL pqq ´∇ p ϕ CDL pqq} ď δ with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof Notice that we have

sup qPS n´1 }grad ϕ CDL pqq ´grad p ϕ CDL pqq} ď sup qPS n´1 }∇ϕ CDL pqq ´∇ p ϕ CDL pqq} ď 1 3θp1 ´θqnp sup qPS n´1 › › P A 0 Xv d3 0 ´AXv d3 › › ď 1 3θp1 ´θqnp ˆsup qPS n´1 › › P A 0 X " v d3 0 ´vd3 ‰› › loooooooooooooooooomoooooooooooooooooon T1 `sup qPS n´1 › › pP A 0 ´Aq Xv d3 › › loooooooooooooooomoooooooooooooooon T2 ˙.

Controlling T 1 . For the first term, we observe

T 1 ď 1 3θp1 ´θqnp }P A 0 } }X} sup qPS n´1 › › v d3 0 ´vd3 › › ,

where for all q P n´1 we have

› › v d3 0 ´vd3 › › ď › › v d2 ´vd2 0 › › 8 }v} `}v ´v0 } }v 0 } 2 8 ď ? K ´?K `}P A 0 } ¯}P A 0 ´A} ˆmax 1ďkďnp }Xe k } ˙2 }X} `}P A 0 ´A} }X} }P A 0 } 2 ˆmax 1ďkďnp }Xe k } ˙2 ď ´?K `}P A 0 } ¯2 }X} ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A}

where for the last two inequalities we used Lemma E.16. Thus, we have

T 1 ď ´?K `}P A 0 } ¯2 }P A 0 } }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

Controlling T 2 . For the second term, by Lemma E.16, we have

T 2 ď }P A 0 ´A} }X} }v} 3 6 ď K 3{2 }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

Summary. Putting all the bounds together, we have sup

qPS n´1 }grad ϕ CDL pqq ´grad p ϕ CDL pqq} ď 1 3θp1 ´θqnp " ´?K `}P A 0 } ¯2 }P A 0 } `K3{2  }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

By Lemma E.17 and Lemma E.20, we have

}X} ď 2 a θmp, max 1ďkďnp }Xe k } ď 4 ? θm logpKpq

with probably at least 1 ´2p ´2. On the other hand, by Lemma E.19, there exists some constant C ą 0, for any P p0, 1q whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q

´2 logpmKq,

we have }P A 0 ´A} ď , }P A 0 } ď 2 ? K

hold with probability at least 1 ´c1 pmKq ´c2 for some numerical constants c 1 , c 2 ą 0. These together give T 1 ď CK 5{2 θm log 2 pKmq .

Replacing δ " CK 5{2 θm log 2 pKmq gives the desired result.

Here, the perturbation analysis for gradient also leads to the following result Corollary E.14 For some small δ P p0, 1q, under the same setting of Proposition E.13, we have sup

qPS n´1

|ϕ CDL pqq ´p ϕ CDL pqq| ď δ hold with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 ą 0 are some numerical constants.

Proof Under the same setting of Proposition E.13, we have

sup qPS n´1 |ϕ CDL pqq ´p ϕ CDL pqq| " sup qPS n´1 1 4 ˇˇˇ1 3θp1 ´θqnp }v 0 } 4 4 ´1 3θp1 ´θqnp }v} 4 4 ˇˇ" sup qPS n´1 1 4 ˇˇˇ1 3θp1 ´θqnp @ q, P A 0 Xv d3 0 ´AXv d3 D ˇˇď 1 4 sup qPS n´1

}∇ϕ CDL pqq ´p ϕ CDL pqq} ď δ 4 , as desired.

E.5.2 CONCENTRATION AND PRECONDITIONING FOR RIEMANNIAN HESSIAN:

simplicity, let v 0 and v be as introduced in Equation (E.13). Similarly, the Riemannian Hessian of ϕ CDL pqq and p ϕ CDL pqq can be written as

Hess ϕ CDL pqq " ´1 3θp1 ´θqnp P q K " 3 pP A 0 q X diag `vd2 0 ˘XJ pP A 0 q J ´}v 0 } 4 4 I ı P q K , Hess p ϕ CDL pqq " ´1 3θp1 ´θqnp P q K " 3AX diag `vd2 ˘XJ A J ´}v} 4 4 I ı P q K ,

respectively. In the following, we show that the difference between grad ϕ CDL pqq and grad p ϕ CDL pqq is small. Proposition E.15 Suppose θ P `1 m , 1 2 ˘. For any δ P p0, 1q, whenever p ě CθK 10 κ 6 pA 0 q σ 2 min pA 0 q δ ´2n 2 log 5 pmKq, we have

sup qPS n´1

}Hess ϕ CDL pqq ´Hess p ϕ CDL pqq} ď δ with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof Notice that

sup qPS n´1 }Hess ϕ CDL pqq ´Hess p ϕ CDL pqq} ď 1 θp1 ´θqnp sup qPS n´1 › › ›pP A 0 ´Aq X diag `vd2 0 ˘XJ pP A 0 q J › › › looooooooooooooooooooooooooooooomooooooooooooooooooooooooooooooon T1 `1 θp1 ´θqnp sup qPS n´1 › › ›AX diag `vd2 ˘X pP A 0 ´Aq J › › › loooooooooooooooooooooooooomoooooooooooooooooooooooooon T2 `1 θp1 ´θqnp sup qPS n´1 › › ›AX diag `vd2 0 ´vd2 ˘XJ pP A 0 q J › › › loooooooooooooooooooooooooooomoooooooooooooooooooooooooooon T3 `1 3θp1 ´θqnp sup qPS n´1 ˇˇ}v} 4 4 ´}v 0 } 4 4 ˇľ ooooooomooooooon T4 .

By using Lemma E.16, we have

T 1 ď }P A 0 } }X} 2 }P A 0 ´A} sup qPS n´1 }v 0 } 2 8 ď }P A 0 } 3 }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} , T 2 ď }A} }X} 2 sup qPS n´1 }v} 2 8 ď K 3{2 }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

Similarly, Lemma E.16 implies that

EQUATION

T 4 ď sup qPS n´1 ˇˇ}v} 4 ´}v 0 } 4 4 ˇˇď 2 sup qPS n´1 ˇˇ@ v ´v0 , 4v d3 Dˇď 8 sup qPS n´1 }v ´v0 } }v} 3 6 ď 8K 3{2 }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

Thus, combining all the results above, we obtain

sup qPS n´1 }Hess ϕ CDL pqq ´Hess p ϕ CDL pqq} ď 1 θp1 ´θqnp "´? K `}P A 0 } ¯}P A 0 } 2 `K }P A 0 } `4K 3{2 ı }X} 2 ˆmax 1ďkďnp }Xe k } ˙2 }P A 0 ´A} .

By Lemma E.17 and Lemma E.20, we have

}X} ď 2 a θmp, max 1ďkďnp }Xe k } ď 4 ? θm logpKpq

with probably at least 1 ´2p ´2. On the other hand, by Lemma E.19, there exists some constant C ą 0, for any P p0, 1q whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q

´2 logpmKq, we have

}P A 0 ´A} ď , }P A 0 } ď 2 ? K

hold with probability at least 1 ´c1 pmKq ´c2 for some numerical constants c 1 , c 2 ą 0. These together gives

sup qPS n´1 }Hess ϕ CDL pqq ´Hess p ϕ CDL pqq} ď C 1 K 5{2 θm log 2 pKpq .

Replacing δ " C 1 K 5{2 θm log 2 pKpq gives the desired result.

E.5.3 AUXILIARY RESULTS:

Lemma E.16 Let v 0 and v be defined as in Equation (E.13), with v 0 pqq " X J pP A 0 q J q, vpqq " X J A J q, For all q P S n´1 , we have

}v} 8 ď ? K max 1ďkďnp }Xe k } , }v 0 } 8 ď }P A 0 } max 1ďkďnp }Xe k } , }v} ď ? K }X} , }v} 6 6 ď K 3 }X} 2 ˆmax 1ďkďnp }Xe k } ˙4 , › › v d2 ´vd2 0 › › 8 ď ´?K `}P A 0 } ¯}P A 0 ´A} ˆmax 1ďkďnp }Xe k } ˙2 , }v ´v0 } ď }P A 0 ´A} }X} .

Proof In the following, we bound each term, respectively.

Bounding norms of v and v 0 . the 2 -norm, notice that }v} ď }X} }A} ď ? K }X}

On the other hand, for the 8 -norm, we have

}v} 8 " max 1ďkďnp › › e J k X J A J q › › ď ? K max 1ďkďnp }Xe k } }v 0 } 8 " max 1ďkďnp › › ›e J k X J pP A 0 q J q › › › ď }P A 0 } max 1ďkďnp }Xe k } .

Thus, the results above give

}v} 6 6 ď }v} 4 8 }v} 2 ď K 3 }X} 2 ˆmax 1ďkďnp }Xe k } ˙4 .

Bounding the difference between v and v 0 . First, we bound the difference in 2 -norm,

}v ´v0 } " › › ›X J pP A 0 ´Aq J q › › ď }P A 0 ´A} }X} . On the other hand, we have › › v d2 ´vd2 0 › › 8 ď }v ´v0 } 8 }v `v0 } 8 ď p}v} 8 `}v 0 } 8 q }v ´v0 } 8 , where }v ´v0 } 8 " max 1ďkďnp › › ›e J k X J pP A 0 ´Aq J q › › › ď }P A 0 ´A} max 1ďkďnp }Xe k } ,

Thus, we obtain

EQUATION

Lemma E.17 Suppose X satisfies Assumption E.2, we have

max 1ďkďnp }Xe k } ď 4 ? θm logpKpq

with probability at least 1 ´p´2θm .

Proof Let us write

X i " rr x i1 r x i2 ¨¨¨r x in s , with r x ij " » - - s j´1 rx i1 s . . . s j´1 rx iK s fi ffi fl 1 ď i ď p, 1 ď j ď n,

where s r¨s denotes circulant shift of length . Given X " rX 1 ¨¨¨X p s, we have

max 1ďkďnp }Xe k } " max 1ďiďp,1ďjďn }r x ij } " max 1ďiďp,1ďjďn g f f e K ÿ "1 }s j´1 rx i s} 2 ď ? K max 1ďiďp,1ď ďK }x i } .

Next, we bound max 1ďiďp,1ď ďK }x i }. By using Bernstein inequality in Lemma A.5, we obtain

P ´ˇˇ} x i } 2 ´nθ ˇˇě t ¯ď 2 exp ˆ´t 2 4nθ `4t

Ṫhus, by using a union bound, we obtain max 1ďiďp,1ď ďK }x i } ď 4 ? θn logpKpq, with probability at least 1 ´p´2θm . Summarizing the bounds above, we obtain the desired result.

E.6 INTERMEDIATE RESULTS FOR PRECONDITIONING:

Lemma E.18 Suppose X satisfies Assumption E.2. For any P p0, 1q, whenever p ě Cθ ´1K 2 κ 4 pA 0 q σ 4 min pA 0 q δ ´2 logpmq,

we have › › › › › ˆ1 θmp Y Y J ˙´1{2 ´`A 0 A J 0 ˘´1{2 › › › › › ď δ, › › › › › ˆ1 θmp Y Y J ˙1{2 `A0 A J 0 ˘´1{2 ´I› › › › › ď σ min pA 0 q ¨δ,

hold with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof Notice that 1 θmp Y Y J " 1 θmp A 0 XX J A J 0 " A 0 A J 0 loomoon B `A0 ˆ1 θmp XX J ´I˙A J 0 loooooooooooooooomoooooooooooooooon ∆ .

By Lemma E.20, for any P p0, 1{Kq, whenever

p ě Cθ ´1K 2 ´2 logpmKq, we have › › › › 1 θmp XX J ´I› › › › ď

, with probability at least 1 ´c1 pmKq ´c2 . Thus, by the first inequality in Lemma A.10 we observe

› › › › › ˆ1 θmp Y Y J ˙´1{2 ´pA 0 A 0 q ´1{2 › › › › › " › › ›pB `∆q ´1{2 ´B´1{2 › › › ď 4σ ´2 min pBq }∆} ď 4κ 2 pA 0 q σ 2 min pA 0 q › › › › 1 θmp XX J ´I› › › › ď 4κ 2 pA 0 q σ 2 min pA 0 q ¨ .

On the other hand, by using the second inequality in Lemma A.10, we have

› › › › › ˆ1 θmp Y Y J ˙1{2 `A0 A J 0 ˘´1{2 ´I› › › › › " › › ›pB `∆q 1{2 B ´1{2 ´I› › › ď 4σ ´3{2 min pBq }∆} ď 4κ 2 pA 0 q σ min pA 0 q › › › › 1 θmp XX J ´I› › › › ď 4κ 2 pA 0 q σ min pA 0 q ¨ .

Choose " ´4κ 2 pA0q σ 2 min pA0q

¯´1 δ, we obtain the desired results.

Given the definition of preconditioning matrix P , the result above leads to the following corollary.

Corollary E.19 Under the same settings of Lemma E.18, for any δ P p0, 1q, whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q δ ´2 logpmKq, we have

}P A 0 ´A} ď δ, › › P ´1› › ď 2K ´1{2 }A 0 } , }P A 0 } ď }A} `δ ď ? K `δ

hold with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Proof For the first inequality, we have

}P A 0 ´A} ď ? K › › › › › ˆ1 Y Y J ˙´1{2 ´`A 0 A J 0 ˘´1{2 › › › › › }A 0 } .

Thus, for any δ P p0, 1q, Lemma E.18 implies that whenever p ě Cθ ´1K 3 κ 6 pA 0 q σ 2 min pA 0 q δ ´2 logpmKq, we have

}P A 0 ´A} ď δ, }P A 0 } ď }A} `}P A 0 ´A} ď ? K `δ

with probability at least 1 ´c1 pmKq ´c2 . On the other hand, by Lemma E.18 we have

› › P ´1› › ď › › ›P ´1 ´`K ´1A 0 A 0 ˘1{2 › › › `› › › `K´1 A 0 A 0 ˘1{2 › › › ď › › › `K´1 A 0 A 0 ˘1{2 › › › ´1 `› › ›P ´1 `K´1 A 0 A 0 ˘´1{2 ´I› › › ď K ´1{2 }A 0 } ˜1 `› › › › › ˆ1 θmp Y Y J ˙1{2 `A0 A J 0 ˘´1{2 ´I› › › › › ¸ď 2K ´1{2 }A 0 } , as desired.

Lemma E.20 Suppose X satisfies Assumption E.2. For any δ P p0, 1q, we have

› › › › 1 θmp XX J ´I› › › › ď δ, }X} ď a θmp p1 `δq with probability at least 1 ´c1 mK exp ´´c 2 θp min ! `δ K ˘2 , δ K )¯.

Here, c 1 , c 2 ą 0 are some numerical constants.

Proof By using the fact that X " rX 1 X 2 ¨¨¨X p s, we observe

XX J " p ÿ k"1 X k X J k , X k " » - - C x k1 . . . C x kK fi ffi fl

For any z P S n´1 , write z "

» - - z 1 . . . z K fi ffi fl. We have › › › › 1 θmp XX J ´I› › › › " sup zPS n´1 ˇˇˇz J ˆ1 θmp XX J ´I˙zˇˇˇ" sup zPS n´1 ˇˇˇˇ1 θmp z J ˜p ÿ i"1 X i X J i ¸z ´}z} 2 ˇˇˇ" sup zPS n´1 ˇˇˇˇˇ1 θmp p ÿ i"1 ˜K ÿ k"1 C x ik z k ¸J ˜K ÿ i"1 C x ik z k ¸´}z} 2 ˇˇˇˇ" sup zPS n´1 ˇˇˇˇ1 θmp p ÿ i"1 ˜K ÿ k"1 z J k C J x ik C x ik z k `2 ÿ k " z J k C J x ik C x i z ¸´}z} 2 ˇˇˇď sup zPS n´1 K ÿ k"1 ˇˇˇˇz J k ˜1 θmp p ÿ i"1 C J x ik C x ik ´I¸z k ˇˇˇˇ`2 ÿ k " ˇˇˇˇz J k ˜1 θmp p ÿ i"1 C J x ik C x i ¸z ˇˇˇď K ´1 K ÿ k"1 › › › › › 1 θnp p ÿ i"1 C J x ik C x ik ´I› › › › › `2K ´1 ÿ k " › › › › › 1 θnp p ÿ i"1 C J x ik C x i › › › › ›

.

By Lemma E.21, we obtain

› › › › 1 θmp XX J ´I› › › › ď 1 `2Kt 2 ď δ with probability at least 1 ´2m exp `´c 1 θp min δ 2 , δ (˘´2 mK exp ´´c 2 θp min ! `K´1 δ ˘2 , K ´1δ )¯.

Finally, the second inequality directly follows from the fact that

› › › › 1 θmp XX J ´I› › › › ď δ ùñ }X}

2 ď pθmpq p1 `δq , as desired.

Lemma E.21 Suppose x ij satisfies Assumption E.2. For any j P rKs, we have

› › › › › 1 θnp p ÿ i"1 C J xij C xij ´I› › › › › ď t 1

holding with probability at least 1 ´2m exp ´´θp 8 min

! t 2 1 2 , t 1 )¯.

Moreover, for any k, P rKs with k " , we have

› › › › › 1 θnp p ÿ i"1 C J x ik C x i › › › › › ď t 2

holding with probability at least 1 ´2 m 2 n exp ´´θp 2 min t 2 2 , t 2 ( ¯.

Proof Notice that

C J xij C xij " F ˚diag ´|F x ij | d2 ¯F , C J x ik C x i " F ˚diag `F x ik d F x i ˘F . (E.14) Bounding › › › 1 θnp ř p i"1 C J xij C xij ´I› › ›. From Equation (E.14), we have › › › › › 1 θnp p ÿ i"1 C J xij C xij ´I› › › › › " › › › › › F ˚diag ˜1 θnp p ÿ i"1 |F x ij | d2 ´1¸F › › › › › ď › › › › › 1 θnp p ÿ i"1 |F x ij | d2 ´1› › › › › 8 .

Let f k be a row of F , by Lemma A.3 we have for any ě 1,

E " |f k x ij | 2 ı ď 2 ! 2 E b k "Berpθq " }b k d f k } 2 ı ď ! 2 θp2nq .

Thus, by Bernstein inequality in Lemma A.5, we have

P ˜ˇˇˇˇ1 θnp p ÿ i"1 |f k x ij | d2 ´1ˇˇˇˇˇě t 1 ¸ď 2 exp ˆ´pθt 2 1 8 `4t 1 ˙.

Thus, by using union bounds, we obtain

› › › › › 1 θnp p ÿ i"1 C J xij C xij ´I› › › › › ď › › › › › 1 θnp p ÿ i"1 |F x ij | d2 ´1› › › › › 8 ď t 1

for all 1 ď j ď K with probability at least 1 ´2nK exp ´´θp 8 min

! t 2 1 2 , t 1 )¯. Bounding › › › 1 θnp ř p i"1 C J x ik C x i › › ›.

the other hand, by Equation (E.14), we know that

› › › › › 1 θnp p ÿ i"1 C J x ik C x i › › › › › ď › › › › › 1 θnp p ÿ i"1 F x ik d F x i › › › › › 8 . Let z k id " f d x ik f d x i " x J ik f d f d x i (1 ď d ď n), we have its moments for s ě 1 E " ˇˇz k id ˇˇs ı ď E " ˇˇx J ik f d ˇˇs ı E " |f d x i | s ‰ ď s! 2 E b d "Berpθq " }b d d f d } 2s ı ď s! 2 θn s .

Thus, by Bernstein inequality in Lemma A.5, we obtain

P ˜1 θnp ˇˇˇˇp ÿ i"1 z k id ˇˇˇˇě t 2 ¸ď 2 exp ˆ´θpt 2 2 2 `2t 2 ˙.

Thus, by applying union bounds, we have

› › › › › 1 θnp p ÿ i"1 C J x ik C x i › › › › › ď t 2

for all 1 ď k, ď K and k " with probability at least 1 ´2mK exp ´´θp 2 min t 2 2 , t 2 ( ¯.

F MEASURE CONCENTRATION:

In this part of the appendix, we show measure concentration of Riemannian gradient and Hessian for both ϕ DL pqq and ϕ CDL pqq over the sphere. Before that, we first show the following preliminary results that are key for our proof. For simplicity, we also use K " m{n throughout the section.

F.1 PRELIMINARY RESULTS:

Here, as the gradient and Hessian of 4 -loss is heavy-tailed, traditional concentration tools do not directly apply to our cases. Therefore, we first develop some general tools for concentrations of superema of heavy-tailed empirical process over the sphere. In later part of this appendix, we will apply these results for concentration of Riemannian gradient and Hessian for both overcomplete dictionary learning and convolutional dictionary learning.

Theorem F.1 (Concentration of heavy-tailed random matrices over the sphere) Let Z 1 , Z 2 , ¨¨¨, Z p P R n1ˆn2 be i.i.d. centered subgaussian random matrices, with Z i " d Z p1 ď i ď pq and

E rZ ij s " 0, P p|Z ij | ą tq ď 2 exp ˆ´t 2 2σ 2 ˙.

For a fixed q P S n´1 , let us define a function f q p¨q : R n1ˆn2 Þ Ñ R d1ˆd2 , such that 1. f q pZq is a heavy tailed process of Z, in the sense of P `}f q pZq} ě t ˘ď 2 exp `´C ? t ˘.

2. The expectation E rf q pZqs is bounded and L f -Lipschitz, i.e., }E rf q pZqs} ď B f , and }E rf q1 pZqs ´E rf q2 pZqs} ď L f }q 1 ´q2 } , @ q 1 , q 2 P S n´1 . (F.1)

3. Let Z be a truncated random matrix of Z, such that

Z " Z `p Z, Z ij " " Z ij if |Z ij | ă B, 0 otherwise. (F.2)

with B " 2σ a log pn 1 n 2 pq. For the truncated matrix Z, we further assume that

› › f q pZq › › ď R 1 pσq, max › › E " f q pZq J f q pZq ‰› › , › › f q pZqf q pZq J › › ( ď R 2 pσq, (F.3) › › f q1 pZq ´fq2 pZq › › ď L f pσq }q 1 ´q2 } , @ q 1 , q 2 P S n´1 .

(F.4)

Then for any δ P ´0, 6 R2 R1 ¯, whenever

p ě C max # min td 1 , d 2 u B f n 1 n δ , δ ´2R 2 « n log ˜6 `Lf `Lf δ ¸`logpd 1 `d2 q ff+ we have sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ď δ,

holding with probability at least 1 ´pn 1 n 2 pq ´2 ´n´c logppL f `Lf q{δq for some constant c, C ą 0.

Proof As aforementioned, traditional concentration tools does not directly apply due to the heavytailed behavior of f q pZq. To circumvent the difficulties, we first truncate Z and introduce bounded random variable Z as in Equation (F.2), with truncation level B " 2σ a log pn 1 n 2 pq. Thus, we have

P ˜sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ḑ P ˜sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ļooooooooooooooooooooooooooooomooooooooooooooooooooooooooooon P1ptq `P ˆmax 1ďiďp }Z i } 8 ě B loooooooooooooomoooooooooooooon P2 .

As f q pZq is also bounded, then we can apply classical concentration tools to P 1 ptq, and bound P 2 by using subgaussian tails of Z. In the following, we make this argument rigorous with more technical details.

Tail bound for P 2 . Since Z i jk is centered subgaussian, by an union bound, we have

P 2 " P ˆmax 1ďiďp }Z i } 8 ě B ˙ď n 1 n 2 pP `ˇZ i jk ˇˇě B ˘ď exp ˆ´B 2 2σ 2 `log pn 1 n 2 pq ˙.

Choose B " 2σ a log pn 1 n 2 pq, we obtain

P 2 " P ˆmax 1ďiďp }Z i } 8 ě B ˙ď pn 1 n 2 pq ´2 .

Tail Bound for › › › 1 p ř p i"1 f q pZ i q ´E rf q pZqs › › › with a fixed q P S n´1 . First, we control the quantity for a given q P S n´1 . Later, we will turn the tail bound result to a uniform bound over the sphere for all q P S n´1 . We first apply triangle inequality, where we have

› › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ď › › › › › 1 p p ÿ i"1 f q pZ i q ´E " f q pZq ‰ › › › › › `› › E rf q pZqs ´E " f q pZq ‰› › , such that P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ḑ P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E " f q pZq ‰ › › › › › ě t ´› › E rf q pZqs ´E " f q pZq ‰› › ¸. Notice that › › E " f q pZq ‰ ´E rf q pZqs › › ď › › E " f q pZq d 1 Z‰Z ‰› › F ď }E rf q pZqs} F › › E " 1 Z‰Z ‰› › F ď min td 1 , d 2 u B f d ÿ ij P `Zij " Z ij ď min td 1 , d 2 u B f d n 1 n 2 exp ˆ´B 2 2σ 2 ˙,

where for the second inequality we used Cauchy-Schwarz inequality, the third one follows from and the last one follows from the fact in Z is With B " 2σ a log pn 1 n 2 pq, we obtain

› › E " f q pZq ‰ ´E rf q pZqs › › ď min td 1 , d 2 u B f n 1 n 2 p , so that P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ¸ď P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E " f q pZq ‰ › › › › › ě t ´Bf n 1 n 2 p ¸.

Next, we need to show concentration of

› › › 1 p ř p i"1 f q pZ i q ´E " f q pZq ‰ › › ›

to finish this part of proof. By our assumption in Equation (F.3), we apply bounded Bernstein's inequality in Lemma A.7, such that

P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E " f q pZq ‰ › › › › › ě t 1 ¸ď pd 1 `d2 q exp ˆ´pt 2 1 2R 2 `4R 1 t 2 {3 ˙.

Choose p large enough such that

p ě 2 min td 1 , d 2 u B f n 1 n 2 t ùñ min td 1 , d 2 u B f n 1 n 2 p ď t 2 .

Thus, for a fixed q P S n´1 , we have

P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ¸ď P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E " f q pZq ‰ › › › › › ě t{2 ḑ pd 1 `d2 q exp ˆ´pt 2 8R 2 `8R 1 t{3 ˙.

Bounding P 1 ptq via covering over the sphere S n´1 . Finally, we finish by . Let N p q be an epsilon net of the sphere, where we know that @ q P S n´1 , D q 1 P N p q, s.t.

› › q ´q1 › › ď , and #N p q ď ˆ3 ˙n´1 .

Thus, we have

sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › " sup q 1 PN p q,}e}ď › › › › › 1 p p ÿ i"1 f q 1 `epZ i q ´E rf q 1 `epZqs › › › › › ď sup q 1 PN p q › › › › › 1 p p ÿ i"1 f q 1 pZ i q ´E rf q 1 pZqs › › › › › `sup q 1 PN p q,}e}ď › › › › › 1 p p ÿ i"1 f q 1 `epZ i q ´1 p p ÿ i"1 f q 1 pZ i q › › › › › `sup q 1 PN p q,}e}ď

}E rf q 1 `epZqs ´E rf q 1 pZqs} .

By our Lipschitz continuity assumption in Equation (F.1) and Equation (F.4), for any q P S n´1 , we obtain

}E rf q 1 `epZqs ´E rf q 1 pZqs} ď L f }e} , › › › › › 1 p p ÿ i"1 f q 1 `epZ i q ´1 p p ÿ i"1 f q 1 pZ i q › › › › › ď › › f q 1 `epZq ´fq 1 pZq › › ď L f }e} , which implies that sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ď sup q 1 PN p q › › › › › 1 p p ÿ i"1 f q 1 pZ i q ´E rf q 1 pZqs › › › › › ``L f `Lf ˘ .

Therefore, for any t ą 0, choose ď t 2pL f `Lf q , so that we obtain

P ˜sup qPS n´1 › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t ḑ P ˜sup q 1 PN p q › › › › › 1 p p ÿ i"1 f q 1 pZ i q ´E rf q 1 pZqs › › › › › ě t ´`L f `Lf ˘ ḑ P ˜sup q 1 PN p q › › › › › 1 p p ÿ i"1 f q 1 pZ i q ´E rf q 1 pZqs › › › › › ě t{2 ḑ #N p q ¨P ˜› › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ě t{2 ḑ ˆ3 ˙n´1 pd 1 `d2 q exp ˆ´pt 2 32R 2 `16R 1 t{3 ď exp ˜´min " pt 2 64R 2 , 3pt 32R 1 * `n log ˜6 `Lf `Lf t ¸`logpd 1 `d2 q ¸.

Summary of the results. Therefore, combining all the results above, for any δ P ´0,

6 R2 R1 ¯, whenever p ě C max # min td 1 , d 2 u B f n 1 n 2 δ , δ ´2R 2 « n log ˜6 `Lf `Lf δ ¸`logpd 1 `d2 q ff+ , we have sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pZ i q ´E rf q pZqs › › › › › ď δ,

holding with probability at least 1 ´pn 1 n 2 pq ´2 ´n´c logppL f `Lf q{δq for some constant c, C ą 0.

Corollary F.2 (Concentration of heavy-tailed random vectors over the sphere) Let z 1 , z 2 , ¨¨¨, z p P R n1 be i.i.d. centered subgaussian random matrices, with z i " d z p1 ď i ď pq and

E rz i s " 0, P p|z i | ą tq ď 2 exp ˆ´t 2 2σ 2 ˙.

For a fixed q P S n´1 , let us define a function f q p¨q : R n1 Þ Ñ R d1 , such that 1. f q pzq is a heavy tailed process of z, in the sense of P `}f q pzq} ě t ˘ď 2 exp `´C ? t ˘.

2. The expectation E rf q pzqs is bounded and L f -Lipschitz, i.e., }E rf q pzqs} ď B f , and }E rf q1 pzqs ´E rf q2 pzqs} ď L f }q 1 ´q2 } , @ q 1 , q 2 P S n´1 . (F.5)

3. Let z be a truncated random matrix of z, such that

z " z `p z, z i " " z i if |z i | ă B, 0 otherwise. (F.6)

with B " 2σ a log pn 1 pq. For the truncated matrix z, we further assume that

}f q pzq} ď R 1 pσq, E " }f q pzq} 2 ı ď R 2 pσq, (F.7)

}f q1 pzq ´fq2 pzq} ď L f pσq }q 1 ´q2 } , @ q 1 , q 2 P S n´1 . (F.8)

Then for any δ P ´0, 6 R2 R1 ¯, whenever

p ě C max # B f n 1 δ , δ ´2R 2 « n log ˜6 `Lf `Lf δ ¸`logpd 1 q ff+ , we have sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pz i q ´E rf q pzqs › › › › › ď δ,

holding with probability at least 1 ´pn 1 pq ´2 ´n´c logppL f `Lf q{δq for some constant c, C ą 0.

Proof The proof is analogous to that of Theorem F.1. The slight difference is that we need to apply vector version Bernstein's inequality in Lemma A.8 instead of matrix version in Lemma A.7, by utilizing our assumption in Equation (F.7). We omit the detailed proof here.

F.2 CONCENTRATION FOR OVERCOMPLETE DICTIONARY LEARNING:

In this part of appendix, we assume that the dictionary A is tight frame with 2 -norm bounded columns 1 K AA J " I, }a i } ď M p1 ď i ď mq. (F.9)

for some M with 1 ď M ď ? K.

F.2.1 CONCENTRATION OF grad ϕ DL p¨q:

First, we show concentration of grad ϕ DL pqq to its expectation E rgrad ϕ DL pqqs " grad ϕ T pqq, grad ϕ DL pqq " ´1 3θp1 ´θqp

P q K p ÿ k"1 `qJ Ax k ˘3 pAx k q ÝÑ grad ϕ T pqq " ´Pq K A `AJ q ˘d3 ,

where x k follows i.i.d. BGpθq distribution in Assumption 2.2. Concretely, we have the following result.

Proposition F.3 (Concentration of grad ϕ DL p¨q) Suppose A satisfies Equation (F.9) and X P R mˆp follows BGpθq with θ P `1 m , 1 2 ˘. For any given δ P `0, cK 2 {pm log 2 p log 2 npq ˘, whenever

p ě Cδ ´2θK 5 n 2 log ˆθKn δ ˙, we have sup qPS n´1

}grad ϕ DL pqq ´grad ϕ T pqq} ă δ holds with probability at least 1 ´c1 p ´2. Here, c, c 1 , C ą 0 are some numerical constants.

Proof Since we have

grad ϕ DL pqq " ´1 3θp1 ´θqp P q K p ÿ k"1 `qJ Ax k ˘3 pAx k q ,

we invoke Corollary F.2 to show this result by letting f q pxq " ´1 3θp1 ´θq `qJ Ax ˘3 P q K Ax P R n , (F.10) where x " BGpθq and we need to check the conditions in Equation (F.5), Equation (F.7), and Equation (F.8).

Calculating subgaussian parameter σ 2 for x and truncation. Since each entry of x follows x i " i.i.d. BGpθq, its tail behavior is very similar and can be upper bounded by the tail of Gaussian, i.e.,

P p|x i | ě tq ď exp `´t 2 {2

˘, so that we choose the truncation level B " 2 a log pnpq.

Calculating R 1 and R 2 in Equation (F.7). First, for each i p1 ď i ď pq, we have

}f q px i q} " 1 3θp1 ´θq › › › `qJ Ax i ˘3 P q K Ax i › › › ď }Ax i } 4 3θp1 ´θq ď }A} 4 }x i } 4 3θp1 ´θq ď K 2 }x i } 4 3θp1 ´θq .

By Lemma A.9 and a union bound, we know that for any 1 ď i ď p,

}x i } 0 ď 4θm log p, }x i } 0 ď 4θm log p ùñ }x i } 2 ď B 2 }x i } 0 " 4B 2 θm log p (F.11)

with probability at least 1 ´p´2θm . Thus, by our truncation level, we have w.h.p.

}f q px i q} ď 6θ p1 ´θq K 2 B 4 m 2 log 2 p " R 1 .

On the other hand, by Lemma F.5, for the second moment we have

E " }f q px i q} 2 ı ď E " }f q px i q} 2 ı ď cθK 4 m

for some constant c ą 0. Thus, we obtain

R 1 " 6θ p1 ´θq K 2 B 4 m 2 log 2 p, R 2 " cθK 4 m. (F.12)

Calculating L f in Equation (F.8). Notice that for any q 1 , q 2 P S n´1 , let ζ i " A J q i pi " 1, 2q, by Lemma F.4 we have

}f q1 pxq ´fq2 pxq} " 1 3θp1 ´θq › › › `ζJ 1 x ˘3 P q K 1 Ax ´`ζ J 2 x ˘3 P q K 2 Ax › › › ď }A} }x} 3θp1 ´θq › › › `ζJ 1 x ˘3 P q K 1 ´`ζ J 2 x ˘3 P q K 2 › › › ď }A} }x} 3θp1 ´θq " ˇˇζ J 1 x ˇˇ3 › › ›P q K 1 ´Pq K 2 › › › `ˇˇ`ζ J 1 x ˘3 ´`ζ J 2 x ˘3ˇˇˇı ď }A} }x} 3θp1 ´θq " 2 }A} 3 }x} 3 }q 1 ´q2 } `3 }A} 3 }x} 3 }q 1 ´q2 } ı ď 2 }A} 4 }x} 4 θp1 ´θq }q 1 ´q2 } .

where for the last two inequalities we used Lemma A.11 and

ˇˇ`ζ J 1 x ˘3 ´`ζ J 2 x ˘3ˇˇˇ" ˇˇpζ1 ´ζ2 q J x ˇˇˇˇ`ζ J 1 x ˘2 ``ζ J 1 x ˘`ζ J 2 x ˘``ζ J 2 x ˘2ˇˇď }A} }x} }q 1 ´q2 } " `ζJ 1 x ˘2 ``ζ J 2 x ˘2 `ˇζ J 1 x ˇˇˇˇζ J 2 x ˇˇı ď 3 }A} 3 }x} 3 }q 1 ´q2 } .

Furthermore, by Equation (F.11) we obtain

}f q1 pxq ´fq2 pxq} ď 2 }A} 4 }x} 4 θp1 ´θq }q 1 ´q2 } ď 32θ 1 ´θ K 2 B 4 m 2 log 2 p }q 1 ´q2 } .

This gives

L f " 32θ 1 ´θ K 2 B 4 m 2 log 2 p. (F.13)

Calculating B f and L f in Equation (F.5). From Lemma F.4 we know that E rf q pxqs " P q K Aζ d3 , so that

}E rf q pxqs} " › › ›P q K A `AJ q ˘d3 › › › ď › › P q K › › }A} › › A J q › › 3 6 ď }A} › › A J q › › 3 ď }A} 4 " K 2 " B f , (F.14)

where we used Lemma A.1 for the second inequality. Moreover, we have

}E rf q1 pxqs ´E rf q2 pxqs} ď › › ›P q K 1 Aζ d3 1 ´Pq K 1 Aζ d3 2 › › › `› › ›P q K 1 Aζ d3 2 ´Pq K 2 Aζ d3 2 › › › ď }A} › › ζ d3 1 ´ζd3 2 › › `› › ›P q K 1 ´Pq K 2 › › › }A} › › ζ d3 2 › › ď }A} › › pζ 1 ´ζ2 q d `ζd2 1 `ζ1 d ζ 2 `ζd2 1 ˘› › `2 }A} }ζ 2 } 3 }q 1 ´q2 } ď 5 }A} 4 }q 1 ´q2 } " 5K 2 }q 1 ´q2 } " L f }q 1 ´q2 } . (F.15)

where for the last inequality, we used the fact that

› › pζ 1 ´ζ2 q d `ζd2 1 `ζ1 d ζ 2 `ζd2 1 ˘› › ď }ζ 1 ´ζ2 } 4 › › ζ d2 1 `ζ1 d ζ 2 `ζd2 1 › › 4 ď › › A J pq 1 ´q2 q › › `› › ζ d2 1 › › `}ζ 1 d ζ 2 } `› › ζ d2 1 › › ď 3 }A} 3 }q 1 ´q2 } .

Thus, from Equation (F.14) and Equation (F.15), we obtain

B f " K 2 , L f " 5K 2 . (F.16)

Final calculation. Finally, we are now ready to put all the estimations in Equations (F.12), (F.13) and (F.16) together and apply Corollary F.2 to obtain our result. For any δ P ´0, 6 R2 R1 ¯, whenever p ě Cδ ´2θK 5 n 2 log pθKn{δq , we have

sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pz i q ´E rf q pzqs › › › › › ď δ,

holding with probability at least 1 ´pnpq ´2 ´n´c1 logpθKn{δq ´p´2θm for some constant c 1 , C ą 0.

Lemma F.4 (Expectation of grad ϕ DL p¨q) @q P S n´1 , the expectation of grad ϕ DL p¨q satisfies grad ϕ DL pqq " grad ϕ T pqq " ´Pq K A `AJ q ˘d3

Proof Direct calculation.

Lemma F.5 Suppose x " BGpθq and let f q pxq be defined as Equation (F.10), then we have

E " }f q pxq} 2 ı ď CθK 4 m pK " m{nq.

Proof Since x " BGpθq, we write x " b d g with " " " Berpθq and g " N p0, Iq. Let I be the nonzero support of x with I " supp x. And let P I p¨q be an operator that restricts a vector to the support I, so that we can write x " P I pgq. Notice that

E }f q pxq} 2 " E « m ÿ k"1 " f d2 q pxq ‰ k ff ď m max kPrms E " f d2 q pxq ‰ k .

Let W " P q K A with w k being the k th row of W . For @k P rns,

" Ef d2 q pxq ‰ k " 1 9θ 2 p1 ´θq 2 E » -`qJ Ax ˘6 ˜m ÿ i"1 w k,i x i ¸2fi fl ď 1 9θ 2 p1 ´θq 2 ´E @ A J q, x D 12 ¯1 2 ´E xw k , xy 4 ¯1 2 " 1 9θ 2 p1 ´θq 2 ´E @ P I `AJ q ˘, g D 12 ¯1 2 ´E xP I pw k q , gy 4 ¯1 2 .

Notice that

@ P I `AJ q ˘, v D " N p0, › › P I `AJ q ˘› › 2 q and xP I pw k q , vy " N p0, }P I pw k q} 2 q, hence ´E @ P I `AJ q ˘, v D 12 ¯1 2 " ? 11!! ´EI › › P I `AJ q ˘› › 12 ¯1 2 .

Let A J q " ζ, then we have

E I › › P I `AJ q ˘› › 12 " ÿ k1,k2,...,k6 m 2 k1 1 k1PI ζ 2 k2 1 k2PI ζ 2 k3 1 k3PI ζ 2 k4 1 k4PI ζ 2 k5 1 k5PI ζ 2 k6 1 k6PI , (F.17)

for bounding equation F.17, we discuss the following cases:

• When only one index among k 1 , k 2 , . . . , k 6 is in I:

E I › › P I `AJ q ˘› › 12 " θ ÿ k1 ζ 12 k1 ď θK 6

• When only two indices among k 1 , k 2 , . . . , k 6 are in I:

E I › › P I `AJ q ˘› › 12 " θ 2 ÿ k1,k2 `ζ2 k1 ζ 10 k2 `ζ4 k1 ζ 8 k2 `ζ6 k1 ζ 6 k2 ˘ď 3θ 2 K 6

• When only three indices among k 1 , k 2 , . . . , k 6 are in I:

E I › › P I `AJ q ˘› › 12 " θ 3 ÿ k1,k2,k3 `ζ2 k1 ζ 2 k2 ζ 8 k3 `ζ2 k1 ζ 4 k2 ζ 6 k3 `ζ4 k1 ζ 4 k2 ζ 4 k3 ˘ď 3θ 3 K 6

• When only four indices among k 1 , k 2 , . . . , k 6 are in I:

E I › › P I `AJ q ˘› › 12 " θ 4 ÿ k1,k2,k3,k4 `ζ2 k1 ζ 2 k2 ζ 2 k3 ζ 6 k4 `ζ2 k1 ζ 2 k2 ζ 4 k3 ζ 4 k4 ˘ď 2θ 4 K 6

• When only five indices among k 1 , k 2 , . . . , k 6 are in I:

E I › › P I `AJ q ˘› › 12 " θ 5 ÿ k1,k2,k3,k4,k5 `ζ2 k1 ζ 2 k2 ζ 2 k3 ζ 2 k4 ζ 4 k5 ˘ď θ 5 K 6

• When all six indices of k 1 , k 2 , . . . , k 6 are in I:

E I › › P I `AJ q ˘› › 12 " θ 6 ÿ k1,k2,k3,k4,k5,k6 `ζ2 k1 ζ 2 k2 ζ 2 k3 ζ 2 k4 ζ 2 k5 ζ 2 k6 ˘ď θ 6 K 6 .

Hence, we have

E I › › P I `AJ q ˘› › 12 " θK 6 `3θ 2 K 6 `3θ 3 K 6 `2θ 4 K 6 `θ5 K 6 `θ6 K 6 ď C 1 θK 6

for a constant C 1 ą 11. Similarly, we have

´E xP I pw k q , vy 4 ¯1 2 " ? 3 ´EI }P I pw k q} 4 ¯1 2 ,

and

E I }P I pw k q} 4 " ÿ k1,k2 w 2 k,k1 1 k1PI w 2 k,k2 1 k2PI ď C 2 θ m 2 n 2 ,

for a constant C 2 ą 2. Hence, we have

´E @ P I `AJ q ˘, g D 12 ¯1 2 ´E xP I w k , gy 4 ¯1 2 ď C 3 θ m 4 n 4 ,

for a constant C 3 ą 829. Hence, we know that @k P rns, }Hess ϕ DL pqq ´Hess ϕ T pqq} ă δ holds with probability at least 1 ´c1 p ´2. Here, c, c 1 , C ą 0 are some numerical constants.

" Ef d2 q pxq ‰ k ď C 4 θp1 ´θq 2 m 4 n 4 " CθK 4 , for a constant C 4 ą 93. Therefore E }f q pxq} 2 ď

Proof Since we have:

Hess ϕ DL pqq " ´1 3θp1 ´θqp p ÿ k"1 P q K " 3 `qJ Ax k ˘2 Ax k pAx k q J ´`q J Ax k ˘4 I ı P q K , we invoke Theorem F.1 to show our result by letting f q pxq " ´1 3θp1 ´θq P q K " 3 `qJ Ax ˘2 Ax pAxq J ´`q J Ax ˘4 I ı P q K P R nˆn , (F.18)

where x " BGpθq and we need to check the conditions in Equation (F.1), Equation (F.3), and Equation (F.4).

Calculating subgaussian parameter σ 2 for x and truncation. Since each entry of x follows x i " i.i.d. BGpθq, its tail behavior is very similar and can be upper bounded by the tail of Gaussian, i.e.,

P p|x i | ě tq ď exp `´t 2 {2

˘, so that we choose the truncation level B " 2 a log pnpq. By Lemma A.9 and a union bound, we know that for any 1 ď i ď p, }x i } 0 ď 4θm log p, }x i } 0 ď 4θm log p ùñ }x i } 2 ď B 2 }x i } 0 " 4B 2 θm log p (F.19) with probability at least 1 ´p´2θm .

Calculating R 1 and R 2 in Equation (F.3). For simplicity, let ξ " Ax. First of all, we have }f q pxq} " 1 3θp1 ´θq

› › ›P q K " 3 `qJ ξ ˘2 ξξ J ´`q J ξ ˘4 I ı P q K › › › ď 1 3θp1 ´θq `qJ ξ ˘2 › › ›3ξξ J ´`q J ξ ˘2 I › › › ď 4 3θp1 ´θq › › ξ › › 4 ď 4 3θp1 ´θq }A} 4 }x} 4 ď 64B 4 3p1 ´θq

θK 2 m 2 log 2 p.

On the other hand, by Lemma F.7, we have

› › E " f q pxqf q pxq J ‰› › " › › E " f q pxq J f q pxq ‰› › ď › › E

" f q pxq J f q pxq ‰› › ď c 1 θK 4 m 2 , for some numerical constant c 1 ą 0. In summary, we obtain R 1 " 64B 4 3p1 ´θq θK 2 m 2 log 2 p, R 2 " c 1 K 4 θm 2 . (F.20)

Calculating L f in Equation (F.4). For any q 1 , q 2 P S n´1 , we have

}f q1 pxq ´fq2 pxq} " 1 3θp1 ´θq › › ›P q K 1 " 3 `qJ 1 ξ ˘2 ξξ J ´`q J 1 ξ ˘4 I ı P q K 1 ´Pq K 2 " 3 `qJ 2 ξ ˘2 ξξ J

´`q J 2 ξ ˘4 I

ı P q K 2 › › › ď 1 θp1 ´θq › › ›P q K 1 `qJ 1 ξ ˘2 ξξ J P q K 1 ´Pq K 2 `qJ 2 ξ ˘2 ξξ J P q K 2 › › › looooooooooooooooooooooooooooomooooooooooooooooooooooooooooon T1 `1 3θp1 ´θq › › › `qJ 1 ξ ˘4 P q K 1 ´`q J 2 ξ ˘4 P q K 2 › › › looooooooooooooooomooooooooooooooooon T2 ,

where by Lemma A.11, we have

EQUATION

T 2 ď › › › `qJ 1 ξ ˘4 P q K 1 ´`q J 2 ξ ˘4 P q K 1 › › › `› › › `qJ 2 ξ ˘4 P q K 1 ´`q J 2 ξ ˘4 P q K 2 › › ›

ď ´`q J 1 ξ ˘2 ``q J 2 ξ ˘2¯p q 1 `q2 q J ξξ J pq 1 ´q2 q `2 › › ξ

› › 4 }q 1 ´q2 } ď 6 › › ξ › › 4 }q 1 ´q2 } ď 6 }A} 4 }x} 4 }q 1 ´q2 } ď 96K 2 B 4 θ 2 m 2 log 2 p }q 1 ´q2 } ,

where for the last inequality we used Equation (F.19). Therefore, we have }f q1 pxq ´fq2 pxq} ď 96θ 1 ´θ K 2 B 4 m 2 log 2 p }q 1 ´q2 } , so that

L f " 96θ 1 ´θ K 2 B 4 m 2 log 2 p. (F.21)

Calculating B f and L f in Equation (F.1). We have

}E rf q pxqs} " › › ›P q K " 3A diag `ζd2 ˘AJ ´}ζ} 4 4 I ı P q K › › › ď › › ›3A diag `ζd2 ˘AJ ´}ζ} 4 4 I › › › ď 3 }A} 2 }A} 2 1 Ñ 2 `}A} 4 ď K `3M 2 `K˘,

where }A} 1 Ñ 2 " max 1ďkďm }a k } ď M . On the other hand, for any q 1 , q 2 P S n´1 , we have }E rf q1 pxqs ´E rf q2 pxqs} "

› › ›P q K 1 " 3A diag `ζd2 1 ˘AJ ´}ζ 1 } 4 4 I ı P q K 1 ´Pq K 2 " 3A diag `ζd2 2 ˘AJ ´}ζ 2 } 4 4 I ı P q K 2 › › › ď 3 › › ›P q K 1 A diag `ζd2 1 ˘AJ P q K 1 ´Pq K 2 A diag `ζd2 2 ˘AJ P q K 2 › › › looooooooooooooooooooooooooooooooooooomooooooooooooooooooooooooooooooooooooon L1 `› › ›}ζ1} 4 4 P q K 1 ´}ζ 2 } 4 4 P q K 2 › › › loooooooooooooomoooooooooooooon L2 .

By direct calculation, we have

EQUATION

L 2 ď }ζ 1 } 4 4 › › ›P q K 1 ´Pq K 2 › › › `ˇˇ} ζ 1 } 4 4 ´}ζ 2 } 4 4 ˇˇ› › ›P q K 2 › › › ď 2 }A} 4 }q 1 ´q2 } `|}ζ 1 } 4 ´}ζ 2 } 4 | p}ζ 1 } 4 `}ζ 2 } 4 q ´}ζ 1 } 2 4 `}ζ 2 } 2 4 ď 2 }A} 4 }q 1 ´q2 } `}ζ 1 ´ζ2 } p}ζ 1 } `}ζ 2 }q ´}ζ 1 } 2 `}ζ 2 } 2 ď 6 }A} 4 }q 1 ´q2 } " 6K 2 }q 1 ´q2 } .

These together give us }E rf q1 pxqs ´E rf q2 pxqs} ď 6K `K `M 2 ˘}q 1 ´q2 } .

Summarizing everything together, we have

B f " K `3M 2 `K˘, L f " 6K `K `M 2 ˘. (F.22)

Final calculation. Finally, we are now ready to put all the estimations in Equations (F.20) to (F.22) together and apply Theorem F.1 to obtain our result. For any δ P ´0, 6 R2 R1 ¯, whenever p ě Cδ ´2θK 6 n 3 log pθKn{δq , we have

sup qPS n´1 › › › › › 1 p p ÿ i"1 f q pz i q ´E rf q pzqs › › › › › ď δ,

holding with probability at least 1 ´pnpq ´2 ´n´c1 logpθKn{δq ´p´2θm for some constant c 1 , C ą 0.

Lemma F.7 Suppose θ P `1 m , 1 2 ˘. Let f q pxq be defined as in Equation (F.18). We have › › E " f q pxq J f q pxq ‰› › ď CK 4 θm 2 for some numerical constant C ą 0.

Proof Let x " b d g with b " Berpθq and g " N p0, Iq. First, let ξ " Ax, we have › › E " f q pxq J f q pxq ‰› › " › › ›E " 9 `qJ ξ ˘4 P q K ξξ J P q K ξξ J P q K ´6 `qJ ξ ˘6 P q K ξξP q K ``q J ξ ˘8 P q K ı› › › ď 9 › › ›E " `qJ ξ ˘4 P q K ξξ J P q K ξξ J P q K ı› › › looooooooooooooooooooomooooooooooooooooooooon 

T 1 ď C 1 θ 3 m 2 ´m n ¯4 . T 2 " › › ›P q K E " `qJ ξ ˘6 ξξ J ı P q K › › › ď › › ›E " `qJ ξ ˘6 ξξ J ı› › › " E " `qJ ξ ˘6 }ξ} 2 ı ď Epq J ξq 12 ( 1{2 ! E }ξ} 4 ) 1{2 ď ! E @ A J q, x D 12 ) 1{2 ! E }Ax} 4 ) 1{2 " ! E @ P I pA J qq, g D 12 ) 1{2 " ´m n ¯2 Epx J xq 2 * 1{2 ď C 2 E I " › › P I pA J qq › › 12 ı 1{2 " ´m n ¯2 `3mθ `mpm ´1qθ 2 ˘1{2 ď C 2 θ 2 m ´m n ¯4 .

the proof of the first inequality in the last line is omitted, more details can be found in Lemma F.5.

T 3 " E " @ P I `AJ q ˘, g D 8 ı ď C 3 E I " › › P I `AJ q ˘› › 8 ı ď C 3 θ }A} 8 ď C 3 θ ´m n ¯4 .

Hence, summarizing all the results above, we obtain › › E " f q pxq J f q pxq ‰› › ď Cθm 2 ´m n ¯4 as desired.

Lemma F.8 (Expectation of Hess ϕ DL p¨q) @q P S n´1 , the expectation of Hess ϕ DL p¨q satisfies Hess ϕ DL pqq " Hess ϕ T pqq " ´Pq K " 3A diag `pAq J q d2 ˘AJ ´› › q J A › › 4 4 I ı P q K Proof Direct calculation.

F.3 CONCENTRATION FOR CONVOLUTIONAL DICTIONARY LEARNING:

In this section, we show concentration for the Riemannian gradient and Hessian of the following objective for convolutional dictionary learning, Input: Data Y P R nˆp Output: the vector q ‹ 1: Initialize the iterate q p0q randomly, and set a stepsize τ p0q . 2: while not converged do 3:

Compute Riemannian gradient grad ϕpq pkq q " P pq pkq q K ∇ϕpq pkq q.

4:

Update the iterate by q pk`1q " P S n´1 ´qpkq ´τ pkq grad ϕpq pkq q ¯.

5::

Choose a new stepsize τ pk`1q , and set k Ð k `1. 6: end while Algorithm 3 Power Method Input: Data Y P R nˆp Output: the vector q ‹ 1: Randomly initialize the iterate q p0q . 2: while not converged do 3:

Compute the gradient ∇ϕpq pkq q.

4:

Update the iterate by q pk`1q " P S n´1 ´´∇ϕpq pkq q ¯.

Set k Ð k `1. 6: end while Riemannian gradient descent. To optimize the problem, the most natural idea is starting from a random initialization, and taking projected Riemannian gradient descent steps q Ð P S n´1 pq ´τ ¨grad ϕpqqq , grad ϕpqq " P q K ∇ϕpqq, (G.1)

where τ is the stepsize that can be chosen via linesearch or set as a small constant. We summarize this simple method in Algorithm 2.

Power method. In Algorithm 3 we also introduce a simple power method 17 Journée et al. (2010) by noting that the loss function ϕpqq is concave so that the problem is equivalent to maximizing a convex function. For each iteration, we simply update q by q Ð P S n´1 p´∇ϕpqqq which is parameter-free and enjoys much faster convergence speed. We summarized the method in Algorithm 3. Notice that the power iteration can be interpreted as the Riemannian gradient descent with varied step sizes in the sense that P S n´1 pq ´τ ¨grad ϕpqqq " P S n´1 ˆ´τ ∇ϕpqq ``1 ´τ ¨qJ ∇ϕpqq loooooooooomoooooooooon "0 q ˙" P S n´1 p´∇ϕpqqq by setting τ " 1 q J ∇ϕpqq .

G.2 FAST IMPLEMENTATION OF CDL VIA FFT:

Given the problem setup of CDL in Section 3, in the following we describe more efficient implementation of solving CDL using convolution and FFTs. Namely, we show how to rewrite the gradient of ϕ CDL pqq in the convolutional form. Notice that the preconditioning matrix can be rewrite as a

:

Here, the sparsity level θ denotes the proportion of nonzero entries in X.

Here, for ODL simple means random initializations; for CDL, it means simple data-driven initializations.

The use of

-norm can also be justified from the perspective of sum of squares (SOS)(Barak et al., 2015;Ma et al., 2016;Schramm & Steurer, 2017). One can utilize properties of higher order SOS polynomials (such as 4-th order polynomials) to correctly recover columns of A. But the complexity of these methods are quasi-polynomial, and hence much more expensive than the direct optimization approach we consider here.

Recent results show that methods such as trust-region(Absil et al., 2007;Boumal et al., 2018), cubicregularization(Nesterov & Polyak, 2006), curvilinear search(Goldfarb et al., 2017), and even gradient descent(Lee et al., 2016) can provably escape strict saddle points.

5 Here, we use BGpθq for abbreviation of Bernoulli-Gaussian distribution, with sparsity level θ P p0,

1q.6 For instance, when A is random Gaussian matrix, with each entry aij " i.i.d. N p0, 1{nq.

The Riemannian derivatives are similar to ordinary derivatives in Euclidean space, but they are defined in the tangent space of the manifold M " S n´1 . We refer readers toAbsil et al. (2009a) for more details.

Our preliminary investigation indicates that our premature analysis is not tight enough to achieve this.

From Remark 1, for a typical A, we expect µ P r OppnKq ´1{2 q to be diminishing w.r.t. n.

Similar formulation ideas also appeared in(Huang & Anandkumar, 2015) with no theoretical guarantees.

The CDL problem exhibits shift symmetry in the sense that a 0k f x ik " s ra 0k s f s ´ rx ik s, where s r¨s is a circulant shift operator by length . This implies we can only hope to solve CDL up to a shift ambiguity.

Again, the θ here is only for normalization purpose, which does not affect optimization landscape. Similar P is also considered inSun et al. (2016a);Zhang et al. (2018);Qu et al. (2019).

This is because the off diagonal entries are bounded roughly by ? Kµ, which are tiny when µ is small.

See Figure3ofZhang et al. (2018) for an illustration of these estimations.

For simplicity, we use power method (see Algorithm 3) for optimizing without tuning step sizes. In practice, we find both power method and Riemannian gradient descent have similar performance.

The UNTF dictionary is generated byTropp et al. (2005): (i) generate a standard Gaussian matrix A0, (ii) from A0 alternate between preconditioning the matrix and normalize the columns until convergence.

4 .This completes our proof.

Similar approach also appears in(Zhai et al., 2019).

Figures and Tables:

Figure 1: Plots of landscapes ϕ T pqq and ϕ DL pqq over S 2 .Both function values are normalized to r0, 1s. The overcomplete dictionary A is generated to be UNTF, with n " 3 and m " 4. The sparse coefficient X " BGpθq with θ " 0.1 and p " 2 ˆ10 4 . Black dots denote columns of A (target).

ODL: Recovery probability vs. θ.

Figure 3: Simulations for ODL. (a) θ " 0.1; (b) n " 64; (c) n " 64, θ " 0.1; (d) m " 3n, p " 5 ˆ10 4 .

Zhang et al. (2017); Kuo et al. (2019); Zhang et al. (2018); Lau et al. (

Figure 5: Illustration of f pzq in Equation (B.8) when β ą 0.

GEOMETRIC ANALYSIS OF CRITICAL POINTS IN R C Proposition C.1 Assume }δ g pqq} ď µM }ζ}

together with the assumption }∆ H pqq} ă }ζ} 4 4 }ζ} 2 8 and the fact d J Hess ϕpqqd " d J Hess ϕ T pqqd `dJ ∆ H pqqd ď d J Hess ϕ T pqqd `}∆ H pqq} completes the proof.

at least 1 ´cp ´2, sup qPS n´1 }grad ϕ DL pqq ´grad ϕ T pqq} ď µM }ζ}

" rX 1 X 2 ¨¨¨X p s , X i "

Exact recovery. Our results only lead to approximate recovery of the target solutions. To obtain exact solutions, one might need to consider similar rounding steps as introduced in Qu et al. (2016);

Table content: <table><tr><td>Sun et al. (2016b); Qu et al. (2019).</td></tr></table>

This proves Equation (B.11). Similar argument also holds for β ă 0. Thus, we obtain the desired results.B.1.2 GEOMETRIC CHARACTERIZATIONS OF CRITICAL POINTS IN R CBased on the results in Appendix B.1.1, we prove Proposition B.1, showing that there is no spurious local minimizers in R C .

Table content: <table><tr><td colspan="2">Proof [Proof of Proposition B.1] First recall from Lemma B.2, we defined</td></tr><tr><td>α i "</td><td>4 }ζ} 4</td></tr></table>

are smaller than 2|βi| αi ; 2. Only |ζ 1 | is larger than 2|β1| α1 ; 3. At least |ζ 1 | and |ζ 2 | are larger than 2|β1| α1 and 2|β2| α2 , respectively.

Table content: <table/>

}ζ}

Table content: <table><tr><td/><td/><td>2 8 }ζ} 4 4 `}ζ} 4 4 ´}a 1 }</td><td>8 2 ´}ζ} 2</td><td>ď</td></tr><tr><td colspan="4">´3 }ζ} 2 8 }a 1 } 4 `6 }ζ} 4 8 }a 1 } 2 `6µ }ζ} 8 }ζ} 3 3 ´3 }ζ} 2 8 }ζ} 4 4 `}a 1 } 2 }ζ} 4 4 ´}ζ} 2 8 }ζ} 4 4</td></tr><tr><td colspan="2">" ´3 }ζ} 2 8 `6 }ζ} 4 8 `6µ }ζ} 8 }ζ} 3 3 ´4 }ζ} 2 8 }ζ} 4 4 `}ζ}</td><td>4 4</td></tr><tr><td>ď }ζ} 2 8 ´´3 `6 }ζ} 2 8 `6µ }ζ} 2 ´4 }ζ} 4 4 `}ζ} 2</td><td colspan="3">"</td></tr><tr><td>}ζ} 2 8 ´´3 `6 }ζ} 2 8 `6µK ´4 }ζ} 4 4</td><td/><td/></tr></table>

indicating that this type of critical points q P R C is ridable saddle, for which the Riemannian Hessian exhibits negative eigenvalue. Therefore, the critical points in R C are either ridable saddle or near target solutions, so that there is no spurious local minimizer in R C .C.2 NEGATIVE CURVATURE IN R NBy directly using Lemma B.8, we obtain the negative curvature of ϕpqq in R N .

Table content: <table><tr><td>1 20 }ζ} 4 4 , we have v Lemma C.2 Assume</td><td>}∆ H pqq} ă }ζ} 4 4 }ζ} 2 8</td></tr></table>

Suppose A satisfies Equation (2.2) and X P R mˆp follows BGpθq with θ P `1 m , 1 2

Table content: <table><tr><td>as desired.</td><td/><td/></tr><tr><td>D.2 MAIN GEOMETRIC RESULT</td><td/><td/></tr><tr><td colspan="4">Combining Proposition C.1 and Lemma C.2 together with the concentration results of the gradient</td></tr><tr><td colspan="4">and Hessian in Proposition F.3 and Proposition F.6, we obtain the following geometry results of</td></tr><tr><td>overcomplete dictionary learning.</td><td/><td/></tr><tr><td>Theorem D.2</td><td/><td/></tr><tr><td colspan="2">}z} 4 4 ´θ 2p1 ´θq</td><td colspan="2">}z} 4</td></tr><tr><td>" ϕ T pqq</td><td colspan="2">´θ 2p1 ´θq ´m n</td><td>¯2 ,</td></tr></table>

Lemma E.10 Suppose x satisfies Assumption E.2. Let I " supp px q. Whenever θ P m m , 1

Table content: <table><tr><td/><td/><td/><td/><td/><td>¯,</td></tr><tr><td/><td/><td/><td/><td/><td>2</td></tr><tr><td>then we have</td><td/><td/><td/><td/></tr><tr><td/><td/><td>› › P S m´1</td><td/><td colspan="2">`AJ Ax</td><td>˘˘› › 4 4 ě</td><td>1 2θm</td></tr><tr><td colspan="3">with probability at least 1 ´m´c .</td><td/><td/></tr><tr><td colspan="5">Proof By Lemma A.1, we know that for any z,</td></tr><tr><td/><td/><td/><td colspan="3">}z} 4 4 ě }z} ´1 0 }z} 4 ,</td></tr><tr><td>and the fact that</td><td>› › P S m´1 `PI</td><td>`AJ Ax</td><td colspan="3">˘˘› › 0 " }x } 0 , we have</td></tr><tr><td/><td/><td colspan="2">› › P S m´1 `PI</td><td>`AJ Ax</td><td>˘˘› › 4 4 ě }x } ´1 0 .</td></tr><tr><td colspan="2">By Lemma A.9, we have</td><td/><td/><td/></tr><tr><td/><td colspan="3">}x } 0 ď 2θm ùñ</td><td colspan="2">› › P S m´1 `PI</td><td>`AJ Ax</td><td>˘˘› › 4 4 ě</td><td>1 2θm</td></tr><tr><td>as desired.</td><td/><td/><td/><td/></tr></table>

δ hold with probability at least 1 ´c1 pmKq ´c2 . Here, c 1 , c 2 , C ą 0 are some numerical constants.

Table content: <table><tr><td colspan="2">Proof By triangle inequality, we have</td><td/><td/></tr><tr><td>sup qPS n´1</td><td>ˇˇˇϕ CDL pqq ´ˆϕ T pqq</td><td colspan="2">´θ 2p1 ´θq</td><td>K 2 ˙ˇˇď</td></tr><tr><td>sup</td><td colspan="2">|ϕ CDL pqq ´p ϕ CDL pqq|</td><td>`sup</td><td>| p ϕ CDL pqq ´EX r p ϕ CDL pqqs|</td></tr><tr><td>qPS n´1</td><td/><td/><td>qPS n´1</td></tr><tr><td colspan="3">loooooooooooooooooomoooooooooooooooooon</td><td colspan="2">looooooooooooooooooooomooooooooooooooooooooon</td></tr><tr><td/><td>T1</td><td/><td/><td>T2</td></tr></table>

CθK 4 m,

Table content: <table><tr><td>for a constant C ą</td><td>93 θ 2 p1´θq 2 .</td></tr><tr><td colspan="2">F.2.2 CONCENTRATION we have</td></tr><tr><td/><td>sup</td></tr><tr><td/><td>qPS n´1</td></tr></table>

˘4 P q K ξξ J P q K ξξ J P q K ˘4 ξξ J P q K ξξ J I p1 m q, g d2 D 4 ı ď c 1 mθ `c2 m 2 θ 2 `c3 m 3 θ 3 `c4 m 4 θ 4 .(F.24) combine, equation F.23 and equation F.24, yield

Table content: <table><tr><td>Bound</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">T 1 "</td><td>› › ›E</td><td colspan="10">" `qJ ξ ı› › › ď</td><td>› › ›E</td><td>" `qJ ξ ı› › ›</td></tr><tr><td/><td>"</td><td>› › ›E</td><td colspan="4">" `qJ ξ</td><td colspan="3">˘4 › › P q K ξ</td><td colspan="2">› › 2 ξξ J</td><td>ı› › › ď E</td><td>" `qJ ξ ˘4 }ξ} 4</td><td>ı</td><td>ď Epq J ξq 8 ( 1{2 ! E }ξ} 8</td><td>) 1{2</td></tr><tr><td/><td>"</td><td colspan="2">! E</td><td colspan="5">" @ P I pA J qq, g</td><td colspan="4">D 8 ı) 1{2</td><td>"</td><td>´m n</td><td>¯4 E</td><td>" px J xq 4 ‰</td><td>* 1{2</td><td>,</td></tr><tr><td>where</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td>! E</td><td colspan="6">" @ P I A J q, g</td><td colspan="2">D 8 ı) 1 2</td><td>"</td><td>?</td><td>7!! ´EI</td><td>› › P I A J q</td><td>› › 8 ¯1 2</td><td>ď C 1 θ</td><td>´m n</td><td>¯2</td><td>(F.23)</td></tr><tr><td colspan="13">the proof of the last inequality is omitted, more details can be found in Lemma F.5, and</td></tr><tr><td>E</td><td colspan="5">" `xJ x ˘4ı</td><td colspan="2">" E</td><td colspan="5">" xP I x, P I xy 4</td><td>ı</td><td>" E</td><td>" @ P</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>`6 › › ›P q K E</td><td>" `qJ ξ ˘6 ξξ J</td><td>ı</td><td>P q K</td><td>› › ›</td><td>`E " `qJ ξ</td><td>˘8ı</td><td>.</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>loooooooooooooooomoooooooooooooooon</td><td>looooomooooon</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>T1</td><td>T2</td><td>T3</td></tr></table>

Peer review (iclr2020):
[Summary] This paper studies the problem of non-convex optimization for Dictionary Learning (DL) in the situation when the underlying dictionary is over-complete (more basis vectors m than the dimension n). The paper proves that the L4 maximization formulation has a nice global landscape and can be efficiently minimized by (Riemannian) gradient descent, when the over-complete ratio m/n is less than an absolute constant. A similar result is proved for convolutional dictionary learning. [Pros] The theoretical results in this paper provides a solid improvement over the prior understandings on overcomplete DL, a setting that is practically important yet theoretically more challenging than standard orthogonal/complete DL. Specifically, the prior work of (Ge & Ma 2017) shows only a nice local optimization landscape when m > n^{1+eps} and hypothesizes that the global landscape is bad in the same setting (there exists bad local minima out of a certain sub-level set). In comparison, this work proves that at least for m/n <= 3 (roughly), the landscape is globally benign (has the strict saddle property), therefore providing a new understanding that the benign landscape is still preserved from “the other side” where m/n grows mildly above 1. The analysis contains novel technicalities and can be of general interest for understanding the landscape of non-convex problems. The paper also provides experimental evidence that gradient descent converges globally up until m = O(n^2), a broader regime than suggested by the theory (m <= 3n). (Though when m >= n^{1+eps}, the reason of global convergence from random init may be far from the present theory, in that there can be potentially exponentially many bad local min yet gradient descent won’t get trapped.) [Cons] It is still a bit disturbing to see that m/n needs to be bounded by a fixed absolute constant, rather than *any* constant, for the theory to work. From the proofs it seems like this constant (3) may have the potential to be improved, but it is not quite easy to completely get rid of it?