Emile Richard

Guillaume Obozinski

Jean-Philippe Vert

Tight convex relaxations for sparse matrix factorization

Based on a new atomic norm, we propose a new convex formulation for sparse matrix factorization problems in which the number of nonzero elements of the factors is assumed fixed and known. The formulation counts sparse PCA with multiple factors, subspace clustering and low-rank sparse bilinear regression as potential applications. We compute slow rates and an upper bound on the statistical dimension (Amelunxen et al., 2013) of the suggested norm for rank 1 matrices, showing that its statistical dimension is an order of magnitude smaller than the usual ℓ 1 -norm, trace norm and their combinations. Even though our convex formulation is in theory hard and does not lead to provably polynomial time algorithmic schemes, we propose an active set algorithm leveraging the structure of the convex problem to solve it and show promising numerical results.

Introduction

A range of machine learning problems such as link prediction in graphs containing community structure [START_REF] Richard | Link prediction in graphs with autoregressive features[END_REF], phase retrieval [START_REF] Candès | PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF], subspace clustering (Wang et al., 2013) or dictionary learning for sparse coding [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF] amount to solve sparse matrix factorization problems, i.e., to infer a low-rank matrix that can be factorized as the product of two sparse matrices with few columns (left factor) and few rows (right factor). Such a factorization allows for more efficient storage, faster computation, more interpretable solutions, and, last but not least, it leads to more accurate estimates in many situations. In the case of interaction networks for example, the assumption that the network is organized as a collection of highly connected communities which can overlap implies that the adjacency matrix admits such a factorization. More generally, considering sparse low-rank matrices combines two natural forms of sparsity, in the spectrum and in the support, which can be motivated by the need to explain systems behaviors by a superposition of latent processes which only involve a few parameters. Landmark applications of sparse matrix factorization are sparse principal components analysis (SPCA, d 'Aspremont et al., 2007;[START_REF] Zou | Sparse principal component analysis[END_REF] or sparse canonical correlation analysis (SCCA, [START_REF] Witten | A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis[END_REF], which are widely used to analyze high-dimensional data such as genomic data. From a computational point of view, however, sparse matrix factorization is challenging since it typically leads to non-convex, NP-hard problems [START_REF] Moghaddam | Spectral bounds for sparse PCA: Exact and greedy algorithms[END_REF]. For instance, Berthet and Rigollet (2013) noted that solving sparse PCA with a single component is equivalent to the planted clique problem [START_REF] Jerrum | Large cliques elude the Metropolis process[END_REF], a notoriously hard problem when the size of the support is smaller than the square root of size of the matrix. Many heuristics and relaxations have therefore been proposed, with and without theoretical guaranties, to approximatively solve the problems leading to sparse low-rank matrices. A popular procedure is to alternatively optimize over the left and right factors in the factorization, formulating each step as a convex optimization problem [START_REF] Lee | Efficient sparse coding algorithms[END_REF][START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF]. Despite these worst case computational hardness, simple generalizations of the power method have been proposed by [START_REF] Journée | Generalized power method for sparse principal component analysis[END_REF]; [START_REF] Luss | Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint[END_REF]; [START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF] for the sparse PCA problem with a single component. These algorithms perform well empirically and have been proved to be efficient theoretically under mild conditions by [START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF]. Several semidefinite programming (SDP) convex relaxations of the same problem have also been proposed [START_REF] Amini | High-dimensional analysis of semidefinite relaxations for sparse principal components[END_REF][START_REF] Aspremont | A direct formulation for sparse PCA using semidefinite programming[END_REF][START_REF] Aspremont | Optimal solutions for sparse principal component analysis[END_REF].

Based on the rank one approximate solutions, computing multiple principal components of the data is commonly done though successive deflations (Mackey, 2009) of the input matrix. Recently, several authors have investigated the possibility to formulate sparse matrix factorization as a convex optimization problem. [START_REF] Bach | Convex sparse matrix factorizations[END_REF] showed that the convex relaxation of a number of natural sparse factorization are too coarse too succeed, while [START_REF] Bach | Convex relaxations of structured matrix factorizations[END_REF] investigated several convex formulations involving nuclear norms [START_REF] Jameson | Summing and Nuclear Norms in Banach Space Theory[END_REF], similar to the ones we investigate in this paper, and their SDP relaxations. Several authors also investigated the performance of regularizing a convex loss with linear combinations of the ℓ 1 norm and the trace norm, naturally leading to a matrix which is both sparse and low-rank [START_REF] Doan | Finding approximately rank-one submatrices with the nuclear norm and ℓ 1 norms[END_REF][START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF][START_REF] Richard | Estimation of simultaneously sparse and low-rank matrices[END_REF]Richard et al., , 2013[START_REF] Richard | Link prediction in graphs with autoregressive features[END_REF]. This penalty term can be related to the SDP relaxations of d 'Aspremont et al. (2007'Aspremont et al. ( , 2008) ) that penalize the trace and the element-wise ℓ 1 norm of the positive semi-definite unknown. The statistical performance of these basic combinations of the two convex criteria has however been questioned by [START_REF] Krauthgamer | Do semidefinite relaxations really solve sparse PCA?[END_REF]; [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF]. [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF] showed that for compressed sensing applications, no convex combination of the two norms improves over each norm taken alone. [START_REF] Krauthgamer | Do semidefinite relaxations really solve sparse PCA?[END_REF] prove that the SDP relaxations fail at finding the sparse principal component outside the favorable regime where a simple diagonal thresholding algorithm [START_REF] Amini | High-dimensional analysis of semidefinite relaxations for sparse principal components[END_REF] works. Moreover, these existing convex formulations either aim at finding only a rank one matrix, or a low rank matrix whose factors themselves are not necessarily guaranteed to be sparse. In this work, we propose two new matrix norms which, when used as regularizer for various optimization problems, do yield estimates for low-rank matrices with multiple sparse factors that are provably more efficient statistically than the ℓ 1 and trace norms. The price to pay for this statistical efficiency is that, although convex, the resulting optimization problems are NP-hard, and we must resort to heuristic procedures to solve them. Our numerical experiments however confirm that we obtain the desired theoretical gain to estimate low-rank sparse matrices.

Contributions and organization of the paper

More precisely, our contributions are:

• Two new matrix norms (Section 2). In order to properly define matrix factorization, given sparsity levels of the factors denoted by integers k and q, we first introduce in Section 2.1 the (k, q)-rank of a matrix as the minimum number of left and right factors, having respectively k and q nonzeros, required to reconstruct a matrix. This index is a more involved complexity measure for matrices than the rank in that it conditions on the number of nonzero elements of the left and right factors of a matrix. Using this index, we propose in Section 2.2 two new atomic norms for matrices [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]. (i) Considering the convex hull unit operator norm matrices with (k, q)-rank = 1, we build a convex surrogate to low (k, q)-rank matrix estimation problem. (ii) We introduce a polyhedral norm built upon (k, q)-rank = 1 matrices with all non-zero entries of absolute value equal to 1. We provide in Section 2.3 an equivalent characterization of the norms as nuclear norms, in the sense of [START_REF] Jameson | Summing and Nuclear Norms in Banach Space Theory[END_REF], highlighting in particular a link to the k-support norm of Argyriou et al. (2012).

• Using these norms to estimate sparse low-rank matrices (Section 3). We show how several problems such as bilinear regression or sparse PCA can be formulated as convex optimization problems with our new norms, and clarify that the resulting problems can however be NP-hard.

• Statistical Analysis (Section 4). We study the statistical performance of the new norms and compare them with existing penalties. Our analysis goes first in Section 4.1 using slow rate type of upper bounds on the denoising error, which despite sub-optimality gives a first insight on the gap between the statistical performance of our (k, q)-trace norm and that of the ℓ 1 and trace norms. Next we show in Section 4.2, using cone inclusions and estimates of statistical dimension, that our norms are superior to any convex combination of the trace norm and the ℓ 1 norm in a number of different tasks. However, our analysis also shows that the factors gained over the rivals to estimate sparse low-rank matrices vanishes when we use our norm to estimate sparse vectors.

• A working set algorithm (Section 5). While in the vector case the computation remains feasible in polynomial time, the norms we introduce for matrices can not be evaluated in polynomial time. We propose algorithmic schemes to approximately learn with the new norms.

The same norms and meta-algorithms can be used as a regularizer in supervised problems such as bilinear and quadratic regression. Our algorithmic contribution does not consist in providing more efficient solutions to the rank-1 SPCA problem, but to combine atoms found by the rank-1 solvers in a principled way.

• Numerical experiments (Section 6). We numerically evaluate the performance of our new norms on simulated data, and confirm the theoretical results. While our theoretical analysis only focuses on the estimation of sparse matrices with (k, q)-rank one, our simulations allow us to conjecture that the statistical dimension scales linearly with the (k, q)-rank and decays with the overlap between blocks. We also show that our model is competitive with the stateof-the-art on the problem of sparse PCA.

Due to their length and technicality, all proofs are postponed to the appendices.

Notations

For any integers 1 ≤ k ≤ p, [1, p] = {1, . . . , p} is the set of integers from 1 to p and G p k denotes the set of subsets of k indices in [1, p]. For a vector w ∈ R p , w 0 is the number of non-zero coefficients in w, w 1 = p i=1 |w i | is its ℓ 1 norm, w 2 = p i=1 w 2 i 1 2 is its Euclidean norm, w ∞ = max i |w i | is its ℓ ∞ norm and supp(w) ∈ G p w 0 is its support, i.e., the set of indices of the nonzero entries of w. For any I ⊂ [1, p], w I ∈ R p is the vector that is equal to w on I, and has 0 entries elsewhere. Given matrices A and B of the same size, A, B = tr(A ⊤ B) is the standard inner product of matrices. For any matrix Z ∈ R m 1 ×m 2 the notations Z 0 , Z 1 , Z ∞ , Z Fro , Z * , Z op and rank(Z) stand respectively for the number of nonzeros, entry-wise ℓ 1 and ℓ ∞ norms, the standard ℓ 2 (or Frobenius) norm, the trace-norm (or nuclear norm, the sum of the singular values), the operator norm (the largest singular value) and the rank of Z, while supp(

Z) ⊂ [1, m 1 ] × [1, m 2 ]
is the support of Z, i.e., the set of indices of nonzero elements of Z. When dealing with a matrix Z whose nonzero elements form a block of size k × q, supp(Z) takes the form I × J where (I, J) ∈ G m 1 k × G m 2 q . For a matrix Z and two subsets of indices I ⊂ [1, m 1 ] and J ⊂ [1, m 2 ], Z I,J is the matrix having the same entries as Z inside the index subset I × J, and 0 entries outside. This notation should not be confused with the notation Z (IJ ) which we will sometimes use to denote a general matrix with support contained in I × J.

Tight convex relaxations of sparse factorization constraints

In this section we propose two new matrix norms allowing to formulate various sparse matrix factorization problems as convex optimization problems. We start by defining the (k, q)-rank of a matrix in Section 2.1, a useful generalization of the rank which also quantifies the sparseness of a matrix factorization. We then introduce two atomic norms defined as tight convex relaxations of the (k, q)-rank in Section 2.2: the (k, q)-trace norm, obtained by relaxing the (k, q)-rank over the operator norm ball, and the (k, q)-CUT norm, obtained by a similar construction with extra-constraints on the element-wise ℓ ∞ of factors. In Section 2.3 we relate these matrix norms to vector norms using the concept of nuclear norms, establishing in particular a connection of the (k, q)-trace norm for matrices with the k-support norm of Argyriou et al. (2012), and the (k, q)-CUT norm to the vector k-norm, defined as the sum of the k largest components in absolute value of a vector (Bhatia, 1997, Exercise II.1.15).

The (k, q)-rank of a matrix

The rank of a matrix Z ∈ R m 1 ×m 2 is the minimum number of rank-1 matrices (i.e., outer products of vectors of the form ab ⊤ for a ∈ R m 1 and b ∈ R m 2 ) needed to express Z as a linear combination of the form Z = r i=1 a i b ⊤ i . It is a versatile concept in linear algebra, central in particular to solve matrix factorization problems and low-rank approximations. The following definition generalizes this notion to incorporate constraints on the sparseness of the rank-1 elements:

Definition 1 ((k, q)-rank) For a matrix Z ∈ R m 1 ×m 2 , we define its (k, q)-rank as the optimal value of the optimization problem:

min c 0 s.t. Z = ∞ i=1 c i a i b ⊤ i , (a i , b i , c i ) ∈ A m 1 k × A m 2 q × R + , (1)
where for any 1 ≤ j ≤ n, A n j := {a ∈ R n : a 0 ≤ j, a 2 = 1} , that is A n j is the set of ndimensional unit vectors with at most j non-zero components.

When k = m 1 and q = m 2 , we recover the usual notion of rank of a matrix, and a particular solution to (1) is provided by the SVD, for which the vectors (a i ) 1≤i≤r and (b i ) 1≤i≤r form each a collection of orthonormal vectors. In general, however, the (k, q)-rank does not share several important properties of the usual rank, as the following proposition shows:

Proposition 2 (Properties of the (k, q)-rank and associated decompositions) 1. The (k, q)-rank of a matrix Z ∈ R m 1 ×m 2 can be strictly larger than m 1 and m 2 .

2. There might be no solution of (1) such that (a i ) 1≤i≤r or (b i ) 1≤i≤r form a collection of orthonormal vectors.

For k = q = 1, the (1, 1)-SVD decomposes Z as a sum of matrices with only one non-zero element, showing that (1, 1)-rank(Z) = Z 0 . Since A n i ⊂ A n j when i ≤ j, we deduce from the expression of the (k, q)-rank as the optimal value of (1) that the following tight inequalities hold:

∀(k, q) ∈ [1, m 1 ] × [1, m 2 ] , rank(Z) ≤ (k, q)-rank(Z) ≤ Z 0 .
The (k, q)-rank is useful to formulate problems in which a matrix should be modeled as or approximated by a matrix with sparse low rank factors, with the assumption that the sparsity level of the factors is fixed and known. For example, the standard rank-1 SPCA problem consists in finding the symmetric matrix with (k, k)-rank equal to 1 and providing the best approximation of the sample covariance matrix [START_REF] Zou | Sparse principal component analysis[END_REF].

2.2 Two convex relaxations for the (k, q)-rank

The (k, q)-rank is obviously a discrete, nonconvex index, like the rank or the cardinality, leading to computational difficulties when one wants to estimate matrices with small (k, q)-rank. In this section, we propose two convex relaxations of the (k, q)-rank aimed at mitigating these difficulties. They are both instances of the atomic norms introduced by [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF], which we first review.

Definition 3 (Atomic norm) Given a centrally symmetric compact subset A ⊂ R p of elements called atoms, the atomic norm induced by A on R p is the gauge function1 of A, defined by

x A = inf {t > 0 : x ∈ t conv (A)} , (2)
where conv(A) denotes the convex hull of A. [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF] show that the atomic norm induced by A is indeed a norm, which can be rewritten as

x A = inf a∈A c a : x = a∈A c a a, c a ≥ 0, ∀a ∈ A , (3)
and whose dual norm satisfies

x * A := sup { x, z : z A ≤ 1} = sup { x, a : a ∈ A} . (4)
We can now define our first convex relaxation of the (k, q)-rank:

Definition 4 ((k, q)-trace norm) For a matrix Z ∈ R m 1 ×m 2 , the (k, q)-trace norm Ω k,q (Z) is the atomic norm induced by the set of atoms:

A k,q = ab ⊤ : a ∈ A m 1 k , b ∈ A m 2 q .
(5)

In words, A k,q is the set of matrices Z ∈ R m 1 ×m 2 such that (k, q)-rank(Z) = 1 and Z op = 1. Plugging (5) into (3), we obtain an equivalent definition of the (k, q)-trace norm as the optimal value of the following optimization problem:

Ω k,q (Z) = min c 1 : Z = ∞ i=1 c i a i b ⊤ i , (a i , b i , c i ) ∈ A m 1 k × A m 2 q × R + . (6)
Comparing ( 6) to (1) shows that the (k, q)-trace norm is derived from the (k, q)-rank by replacing the non-convex ℓ 0 pseudo-norm of c by its convex ℓ 1 norm in the optimization problem. In particular, in the case k = m 1 and q = m 2 , the (k, q)-trace norm is the usual trace norm (equal to the ℓ 1 -norm of singular values), i.e. the usual relaxation of the rank (which is the ℓ 0 -norm of the singular values). Similarly, when k = q = 1, the (k, q)-trace norm is simply the ℓ 1 norm. Just like the (k, q)-rank interpolates between the ℓ 0 pseudo-norm and the rank, the (k, q)-trace norm interpolates between the ℓ 1 norm and the trace norm. Indeed, since A n i ⊂ A n j when i ≤ j, we deduce from the expression of Ω k,q as the optimal value of (6) that the following tight inequalities hold for any

1 ≤ k ≤ m 1 and 1 ≤ q ≤ m 2 : Ω m 1 ,m 2 (Z) = Z * ≤ Ω k,q (Z) ≤ Z 1 = Ω 1,1 (Z) . (7)
In the case of the trace norm, the optimal decomposition solving ( 6) is unique and is in fact the singular value decomposition of the matrix Z with a i and b i being respectively the left and right singular vectors and c i the singular values. This suggest that we can use the (k, q)-trace norm to generalize the definition of the SVD to sparse SVDs as follows Definition 5 ((k, q)-SVD) For a matrix Z ∈ R m 1 ×m 2 , we call (k, q)-sparse singular value decomposition (or (k, q)-SVD)

any decomposition Z = r i=1 c i a i b ⊤ i that solves (6) with c 1 ≥ c 2 ≥ . . . ≥ c r > 0.
In such a decomposition, we refer to vectors (a i , b i ) 1≤i≤r as a set of left and right (k, q)sparse singular vectors of Z, and to (c i ) 1≤i≤r as the corresponding collection of (k, q)-sparse singular values.

Without surprise, the (k, q)-SVD does not share a number of usual properties of the SVD, when k < m 1 and q < m 2 : Proposition 6

1. The (k, q)-SVD is not necessarily unique.

2. The (k, q)-SVDs do not necessarily solve (1): the number of non-zero (k, q)-sparse singular values of a matrix can be strictly larger than its (k, q)-rank.

3. The (k, q)-sparse left or right singular vectors are not necessarily orthogonal to each other.

In addition to (6), the next lemma provides another explicit formulation for the (k, q)-trace norm, its dual and its sub differential:

Lemma 7 For any Z ∈ R m 1 ×m 2 we have Ω k,q (Z) = inf    (I,J)∈G m 1 k ×G m 2 q Z (I,J) * : Z = (I,J) Z (I,J) , supp(Z (I,J) ) ⊂ I × J    , (8)
and

Ω * k,q (Z) = max Z I,J op : I ∈ G m 1 k , J ∈ G m 2 q . ( 9
)
The subdifferential of Ω k,q at an atom A = ab ⊤ ∈ A k,q with I 0 = supp(a) and

J 0 = supp(b) is ∂Ω k,q (A) = A + Z : AZ ⊤ I 0 ,J 0 = 0, A ⊤ Z I 0 ,J 0 = 0, ∀(I, J) ∈ G m 1 k × G m 2 q A I,J + Z I,J op ≤ 1 . ( 10
)
Our second norm is again an atomic norm, but is obtained by focusing on a more restricted set of atoms. It is motivated by applications where we want to estimate matrices which, in addition to being sparse and low-rank, are constant over blocks, such as adjacency matrices of graphs with non-overlapping communities. For that purpose, consider first the subset of A m k made of vectors whose nonzero entries are all equal in absolute value:

A m k = a ∈ R m , a 0 = k , ∀i ∈ supp(a), |a i | = 1 √ k .
We can then define our second convex relaxation of the (k, q)-rank:

Definition 8 ((k, q)-CUT norm) We define the (k, q)-CUT norm Ω k,q (Z) as the atomic norm induced by the set of atoms

A k,q = ab ⊤ : a ∈ A m 1 k , b ∈ A m 2 q . ( 11
)
In other words, the atoms in A k,q are the atoms of A k,q whose nonzero elements all have the same amplitude.

Our choice of terminology is motivated by the following relation of our norm to the CUT-polytope: in the case k = m 1 and q = m 2 , the unit ball of Ω k,q coincides (up to a scaling factor of √ m 1 m 2 ) with the polytope known as the CUT polytope of the complete graph on n vertices [START_REF] Deza | Geometry of Cuts and Metrics, volume 15 of Algorithms and Combinatorics[END_REF], defined by

CUT = conv {ab ⊤ , a ∈ {±1} m 1 , b ∈ {±1} m 2 } .
The norm obtained as the gauge of the CUT polytope is therefore to the trace norm as Ω k,q is to Ω k,q .

Equivalent nuclear norms built upon vector norms

In this section we show that the (k, q)-trace norm (Definition 4) and the (k, q)-CUT norm (Definition 8), which we defined as atomic norms induced by specific atom sets, can alternatively be seen as instances of nuclear norms considered by [START_REF] Jameson | Summing and Nuclear Norms in Banach Space Theory[END_REF]. For that purpose it is useful to recall the general definition of nuclear norms and the characterization of the corresponding dual norms as formulated in Jameson (1987, Propositions 1.9 and 1.11):

Proposition 9 (nuclear norm) Let • α and • β denote any vector norms on R m 1 and R m 2 , respectively, then

ν(Z) := inf i a i α b i β : Z = i a i b ⊤ i ,
where the infimum is taken over all summations of finite length, is a norm over R m 1 ×m 2 called the nuclear norm induced by • α and • β . Its dual is given by

ν * (Z) = sup {a ⊤ Zb : a α ≤ 1 , b β ≤ 1} . ( 12
)
The following lemma shows that the nuclear norm induced by two atomic norms is itself an atomic norm.

Lemma 10 If • α and • β are two atomic norms on R m 1 and R m 2 induced respectively by two atom sets A 1 and A 2 , then the nuclear norm on R m 1 ×m 2 induced by • α and • β is an atomic norm induced by the atom set:

A = {ab ⊤ : a ∈ A 1 , b ∈ A 2 } . L 1 k-support κ k Figure 1
: Unit balls of 3 norms of interest for vectors of R 3 materialized by their sets of extreme points at which the norm is non-differentiable. Each unit ball is the convex hull of the corresponding sets. In green, the usual ℓ 1 -norm scaled by the factor 1/ √ k = 1/ √ 2, in blue the norm θ 2 (a.k.a. 2-support norm), in red the norm κ 2 (see theorem 11). Vertices of the κ 2 unit ball constitute the A 2,1 set (see definition 8). The set A 2,1 belongs to the unit spheres of all three norms (see proposition 18).

We can deduce from it that the (k, q)-trace norm and (k, q)-CUT are nuclear norms, associated to particular vector norms:

Theorem 11

1. The (k, q)-trace norm is the nuclear norm induced by θ k on R m 1 and θ q on R m 2 , where for any j ≥ 1, θ j is the j-support norm introduced by Argyriou et al. (2012).

2. The (k, q)-CUT norm is the nuclear norm induced by κ k on R m 1 and κ q on R m 2 , where for any j ≥ 1:

κ j (w) = 1 √ j max w ∞ , 1 j w 1 . (13)
For the sake of completeness, let us recall the closed-form expression of the k-support norm θ k shown by Argyriou et al. (2012). For any vector w ∈ R p , let w ∈ R p be the vector obtained by sorting the entries of w by decreasing order of absolute values. Then it holds that Of course, Theorem 11 implies that in the vector case (m 2 = 1), the (k, q)-trace norm is simply equal to θ k and the (k, q)-CUT norm is equal to κ k . A representation of the "sharp edges" of unit balls of θ k , κ k and a appropriately scaled ℓ 1 norm can be found in Figure 1 for the case m 1 = 3 and k = 2. In addition, the following results shows that the dual norms of θ k and κ k have simple explicit forms:

θ k (w) =    k-r-1 i=1 | wi | 2 + 1 r + 1 p i=k-r | wi | 2    1 2 , ( 14
) where r ∈ {0, • • • , k -1} is the unique integer such that | wk-r-1 | > 1
Proposition 12 The dual norms of θ k and κ k satisfy respectively:

θ * k (s) = max I:|I|=k s I 2 and κ * k (s) = 1 √ k max I:|I|=k s I 1 .
To conclude this section, let us observe that nuclear norms provide a natural framework to construct matrix norms from vector norms, and that other choices beyond θ k and κ k may lead to interesting norms for sparse matrix factorization. It is however known since [START_REF] Jameson | Summing and Nuclear Norms in Banach Space Theory[END_REF] (see also [START_REF] Bach | Convex relaxations of structured matrix factorizations[END_REF][START_REF] Bach | Structured sparsity through convex optimization[END_REF] that the nuclear norm induced by vector ℓ 1 -norm is simply the ℓ 1 of the matrix which fails to induce low rank (except in the very sparse case). However [START_REF] Bach | Structured sparsity through convex optimization[END_REF] proposed nuclear norms associated with vectors norms that are similar to the elastic net penalty.

Learning matrices with sparse factors

In this section, we briefly discuss how the (k, q)-trace norm and (k, q)-CUT norm can be used to attack various problems involving estimation of sparse low-rank matrices.

Denoising

Suppose X ∈ R m 1 ×m 2 is a noisy observation of a low-rank matrix with sparse factors, assumed to have low (k, q)-rank. A natural convex formulation to recover the noiseless matrix is to solve:

min Z 1 2 Z -X 2 Fro + λΩ k,q (Z) , (15)
where λ is a parameter to be tuned. Note that in the limit when λ → 0, one simply obtains a (k, q)-SVD of X.

Bilinear regression

More generally, given some empirical risk L(Z), it is natural to consider formulations of the form

min Z L(Z) + λΩ k,q (Z)
to learn matrices that are a priori assumed to have a low (k, q)-rank. A particular example is bilinear regression, where, given two inputs x ∈ R m 1 and x ′ ∈ R m 2 , one observes as output a noisy version of y = x ⊤ Zx ′ . Assuming that Z has low (k, q)-rank means that the noiseless response is a sum of a small number of terms, each involving only a small number of features from either of the input vectors. To estimate such a model from observations (x i , x ′ i , y i ) i=1,...,n , one can consider the following convex formulation:

min Z n i=1 ℓ x ⊤ i Zx ′ i , y i + λΩ k,q (Z) , ( 16
)
where ℓ is a loss function. A particular instance of (16) of interest is the quadratic regression problem, where m 1 = m 2 and x i = x ′ i for i = 1, . . . , n. Quadratic regression combined with additional constraints on Z is closely related to phase retrieval [START_REF] Candès | PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF]. It should be noted that if ℓ is the least-square loss, (16) can be rewritten in the form

min Z 1 2 X (Z) -y 2 2 + λΩ k,q (Z) ,
where X (Z) is a linear transformation of Z, so that the problem is from the point of view of the parameter Z a linear regression with a well chosen feature map.

Subspace clustering

In subspace clustering, one assumes that the data can be clustered in such a way that the points in each cluster belong to a low dimensional space. If we have a design matrix X ∈ R n×p with each row corresponding to an observation, then the previous assumption means that if X (j) ∈ R n j ×p is a matrix formed by the rows of cluster j, there exist a low rank matrix Z (j) ∈ R n j ×n j such that Z (j) X (j) = X (j) . This means that there exists a block-diagonal matrix Z such that ZX = X with low-rank diagonal blocks. This idea, exploited recently by Wang et al. (2013) implies that Z is a sum of low rank sparse matrices; and this property still holds if the clustering is unknown. We therefore suggest that if all subspaces are of dimension k, Z may be estimated via

min Z Ω k,k (Z) s.t. ZX = X .

Sparse PCA

In sparse PCA (d 'Aspremont et al., 2007;[START_REF] Witten | A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis[END_REF][START_REF] Zou | Sparse principal component analysis[END_REF], one tries to approximate an empirical covariance matrix Σn by a low-rank matrix with sparse factors. Although this is similar to the denoising problem discussed in Section 3.1, one may wish in addition that the estimated sparse low-rank matrix be symmetric and positive semi-definite (PSD), in order to represent a plausible covariance matrix. This suggests to formulate sparse PCA as follows:

min Z Σn -Z Fro : (k, k)-rank(Z) ≤ r and Z 0 , ( 17
)
where k is the maximum number of non-zero coefficient allowed in each principal direction. In contrast to sequential approaches that estimate the principal components one by one (Mackey, 2009), this formulation requires to find simultaneously a set of factors which are complementary to one another in order to explain as much variance as possible. A natural convex relaxation of ( 17) is

min Z 1 2 Σn -Z 2 Fro + λΩ k,k (Z) : Z 0 , ( 18
)
where λ is a parameter that controls in particular the rank of the approximation. However, although the solution of ( 18) is always PSD, its (k, k)-SVD leading to Z = r i=1 c i a i b ⊤ i may not be composed of symmetric matrices (if a i = b i ), and even if a i = b j the corresponding c i may be negative, as the following proposition shows:

Proposition 13 1. There might be no decomposition of a PSD matrix attaining its (k, q)-rank (i.e. no solution of (1)) which decomposes it as a sum of symmetric terms.

2. The (k, k)-SVD of a PSD matrix is itself not necessarily a sum of symmetric terms.

3. Some PSD matrices cannot be written as a positive combination of rank one (k, k)-sparse matrices, even for k > 1.

This may be unappealing, as one would like to interpret the successive rank-1 matrices as covariance matrices over a subspace that explain some of the total variance. One may therefore prefer a decomposition with less sparse or more factors, potentially capturing less variance.

One solution is to replace Ω k,k in (18) by another penalty which directly imposes symmetric factors with non-negative weights. This is easily obtained by replacing the set of atoms A k,k in Definition 4 by A k, = {aa ⊤ , a ∈ A k }, and considering the corresponding atomic norm which we denote by Ω k, .

To be precise, Ω k, is not a norm but only a gauge because the set A k, is not centrally symmetric. Instead of ( 18), it possible to use the following convex formulation of sparse PCA:

min Z 1 2 Σn -Z 2 Fro + λΩ k, (Z) . ( 19
)
By construction, the solution of ( 19) is not only PSD, but can be expanded as a sum of matrices Z = r i=1 c i a i a ⊤ i , where for all i = 1, . . . , r, the factor a i is k-sparse and the coefficient c i is positive. This formulation is therefore particularly relevant if Σn is believed to be a noisy matrix of this form. It should be noted however that, by Proposition 13, Ω k, is infinite for some PSD matrices2 , which implies that some PSD matrices cannot be approximated well with this formulation.

NP-hard convex problems

Although the (k, q)-trace norm and related norms allow us to formulate several problems of sparse low-rank matrix estimation as convex optimization problems, it should be pointed out that this does not guarantee the existence of efficient computational procedures to solve them. Here we illustrate this with the special case of the best (k, q)-sparse and rank 1 approximation to a matrix, which turns out to be a NP-hard problem. Indeed, let us consider the three following optimization problems, which are equivalent since they return the same rank one subspace spanned by ab ⊤ :

min (a,b,c)∈A k ×Aq×R + X -cab ⊤ 2 Fro ; max (a,b)∈A k ×Aq a ⊤ Xb ; max Z: Ω k,q (Z)≤1 tr(XZ ⊤ ) . (20)
In particular, if k = q and X = Σ n is an empirical covariance matrix, then the symmetric solutions of the problem considered are the solution to the following rank 1 SPCA problem

max z z ⊤ Σn z : z 2 = 1 , z 0 ≤ k , ( 21
)
which it is known to be NP-hard [START_REF] Moghaddam | Sparse regression as a sparse eigenvalue problem[END_REF]. This shows that, in spite of being a convex formulation involving the (k, q)-trace norm, the third formulation in ( 20) is actually NPhard. In practice, we will propose heuristics in Section 6 to approximate the solution of convex optimization problems involving the (k, q)-trace norm.

4 Statistical properties of the (k, q)-trace norm and the (k, q)-CUT norm

In this section we study theoretically the benefits of using the new penalties Ω k,q and Ω k,q to infer low-rank matrices with sparse factors, as suggested in Section 3, postponing the discussion of how to do it in practice to Section 5. Building upon techniques proposed recently to analyze the statistical properties of sparsity-inducing penalties, such as the ℓ 1 penalty or more general atomic norms, we investigate two approaches to derive statistical guarantees. In Section 4.1 we study the expected dual norm of some noise process, from which we can deduce upper bounds on the learning rate for least squares regression and a simple denoising task. In Section 4.2 we estimate the statistical dimension of objects of interest both in the matrix and vector cases and compare the asymptotic rates, which shed light on the power of the norms we study when used as convex penalties. The results in Section 4.1 are technically easier to derive and contain bounds for a matrix of arbitrary (k, q)-rank. The results provided in Section 4.2 rely on a more involved set of tools, they provide more powerful bounds but we do not derive results for matrices of arbitrary (k, q)-rank.

Performance of the (k, q)-trace norm in denoising

In this Section we consider the simple denoising setting (Section 3.1) where we wish to recover a low-rank matrix with sparse factors Z ⋆ ∈ R m 1 ×m 2 from a noisy observation Y ∈ R m 1 ×m 2 corrupted by additive Gaussian noise:

Y = Z ⋆ + σG ,
where σ > 0 and G is a random matrix with entries i.i.d. from N (0, 1). Given a convex penalty Ω : R m 1 ×m 2 → R, we consider, for any λ > 0, the estimator

Ẑλ Ω ∈ arg min Z 1 2 Z -Y 2 Fro + λΩ(Z) .
The following result, valid for any norm Ω, provides a general control of the estimation error in this setting, involving the dual norm of the noise:

Lemma 14 If λ ≥ σΩ * (G) then Ẑλ Ω -Z ⋆ 2 Fro ≤ 4λΩ(Z ⋆ ) .
This suggests to study the dual norm of a random noise matrix Ω * (G) in order to derive a upper bound on the estimation error. The following result provides such upper bounds, in expectation, for the (k, q)-trace norm as well as the standard ℓ 1 and trace norms:

Proposition 15 Let G ∈ R m 1 ×m 2 be a random matrix with entries i.i.d. from N (0, 1). The expected dual norm of G for the (k, q)-trace norm, the ℓ 1 norm and the trace norm is respectively bounded by:

E Ω * k,q (G) ≤ 4 k log m 1 k + 2k + q log m 2 q + 2q , E G * 1 ≤ 2 log(m 1 m 2 ) , E G * * ≤ √ m 1 + √ m 2 . ( 22
)
To derive an upper bound in estimation errors from these inequalities, we consider for simplicity3 the oracle estimate ẐOracle Ω equal to Ẑλ Ω where λ = σΩ * (G). From Lemma 14 we immediately get the following control of the mean estimation error of the oracle estimator, for any penalty Ω:

E ẐOracle Ω -Z ⋆ 2 Fro ≤ 4σΩ(Z ⋆ )E Ω * (G) . ( 23
)
We can now derive upper bounds in estimation errors for the different penalties in the so-called single spike model, where the signal Z ⋆ consists of an atom ab ⊤ ∈ A k,q , and we observed a noisy matrix Y = ab ⊤ + σG. Since for an atom ab ⊤ ∈ A k,q while ab ⊤ 1 ≤ kq/ (kq) = √ kq, Ω k,q (ab ⊤ ) = ab ⊤ * = 1, we immediately get the following by plugging the upper bounds of Proposition 15 into (23):

(k, q)-trace trace ℓ 1 Ω(Z ⋆ )E Ω * (G) k log m 1 k + q log m 2 q √ m 1 + √ m 2 kq log(m 1 m 2 ) k = √ m m 1/4 √ log m √ m √ m log m
Table 1: Various norms mean square error in denoising an atom ab ⊤ ∈ A k,q corrupted with unit variance Gaussian noise. The column "k = √ m" corresponds to the order of magnitudes in the regime where m = m 1 = m 2 and k = q = √ m.

Corollary 16 When Z ⋆ ∈ A k,q is an atom, the expected errors of the oracle estimators using respectively the (k, q)-trace norm, the ℓ 1 norm and the trace norm are respectively upper bounded by:

E ẐOracle Ω k,q -Z ⋆ 2 Fro ≤ 8 σ k log m 1 k + 2k + q log m 2 q + 2q , E ẐOracle 1 -Z ⋆ 2 Fro ≤ 2σ Z ⋆ 1 2 log(m 1 m 2 ) ≤ 2σ 2kq log(m 1 m 2 ) , E ẐOracle * -Z ⋆ 2 Fro ≤ 2σ( √ m 1 + √ m 2 ) . ( 24
)
Remark 17 It is straightforward to see that if in the latter Corollary 16 the matrix Z ⋆ is the convex combination of r > 1 atoms, a factor r ≥ (k, q)-rank(Z ⋆ ) appears in the upper bounds. This suggests a (sub-)linear dependence of the denoising error in the (k, q)-rank.

To make the comparison easy, orders of magnitudes of these upper bounds are gathered in Table 1 for the case where Z ⋆ ∈ A k,q , and for the case where m 1 = m 2 = m and k = q = √ m. In the later case, we see in particular that the (k, q)-trace norm has a better rate than the ℓ 1 and trace norms, in m 14 instead of m 1 2 (up to logarithmic terms). Note that the largest value of Z ⋆ 1 is reached when Z ⋆ ∈ A k,q and equals √ kq. By contrast, when Z ⋆ ∈ A k,q gets far from A k,q elements then the expected error norm diminishes for the ℓ 1 -penalized denoiser ẐOracle

1 reaching σ 2 log(m 1 m 2 ) on e 1 e ⊤
1 while not changing for the two other norms. Obviously the comparison of upper bounds is not enough to conclude to the superiority of (k, q)-trace norm and, admittedly, the problem of denoising considered here is a special instance of linear regression in which the design matrix is the identity, and, since this is a case in which the design is trivially incoherent, it is possible to obtain fast rates for decomposable norms such as the ℓ 1 or trace norm [START_REF] Negahban | A unified framework for highdimensional analysis of M-estimators[END_REF]; however, slow rates are still valid in the presence of an incoherent design, or when the signal to recover is only weakly sparse, which is not the case for the fast rates. Moreover, the result proved here is valid for matrices of rank greater than 1. We present in the next section more involved results, based on lower and upper bounds on the so-called statistical dimension of the different norms [START_REF] Amelunxen | Living on the edge: Phase transitions in convex programs with random data[END_REF], a measure which is closely related to Gaussian widths.

Performance through the statistical dimension

Powerful results from asymptotic geometry have recently been used by [START_REF] Amelunxen | Living on the edge: Phase transitions in convex programs with random data[END_REF]; [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]; [START_REF] Foygel | Corrupted sensing: Novel guarantees for separating structured signals[END_REF]; Oymak et al. (2013) to quantify the statistical power of a convex nonsmooth regularizer used as a constraint or penalty. These results rely essentially on the fact that if the tangent cone 4 of the regularizer at a point of interest Z is thiner, then the regularizer is more efficient at solving problems of denoising, demixing and compressed sensing of Z. The gain in efficiency can be quantified by appropriate measures of width of the tangent cone such as the Gaussian width of its intersection with a unit Euclidean ball [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF], or the closely related concept of statistical dimension of the cone, proposed by [START_REF] Amelunxen | Living on the edge: Phase transitions in convex programs with random data[END_REF]. In this section, we study the statistical dimensions induced by different matrix norms in order to compare their theoretical properties for exact or approximate recovery of sparse low-rank matrices. In particular, we will consider the norms Ω k,q , Ω k,q and linear combinations of the ℓ 1 and trace norms, which have been used in the literature to infer sparse lowrank matrices [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF][START_REF] Richard | Estimation of simultaneously sparse and low-rank matrices[END_REF]. For convenience we therefore introduce the notation Γ µ for the norm that linearly interpolates between the trace norm and the (scaled

) ℓ 1 norm: ∀µ ∈ [0, 1], ∀Z ∈ R m 1 ×m 2 , Γ µ (Z) := µ √ kq Z 1 + (1 -µ) Z * , (25)
so that Γ 0 is the trace norm and Γ 1 is the ℓ 1 norm up to a constant5 .

The statistical dimension and its properties

Let us first briefly recall what the statistical dimension of a convex regularizer Ω : R m 1 ×m 2 → R refers to, and how it is related to efficiency of the regularizer to recover a matrix Z ∈ R m 1 ×m 2 . For that purpose, we first define the tangent cone T Ω (Z) of Ω at Z as the closure of the cone of descent directions, i.e.,

T Ω (Z) := τ >0 {H ∈ R m 1 ×m 2 : Ω(Z + τ H) ≤ Ω(Z)} . (26)
The statistical dimension S(Z, Ω) of Ω at Z can then be formally defined as

S(Z, Ω) := E Π T Ω (Z) (G) 2 Fro , ( 27
)
where G is a random matrix with i.i.d. standard normal entries and Π T Ω (Z) (G) is the orthogonal projection of G onto the cone T Ω (Z). The statistical dimension is a powerful tool to quantify the statistical performance of a regularizer in various contexts, as the following non-exhaustive list of results shows.

• Exact recovery with random measurements. Suppose we observe y = X (Z ⋆ ) where X : R m 1 ×m 2 → R n is a random linear map represented by random design matrices X i i = 1, . . . , n having iid entries drawn from N (0, 1/n). Then Chandrasekaran et al. (2012, Corollary 3.3) shows that

Ẑ = arg min Z Ω(Z) s.th. X (Z) = y (28)
is equal to Z ⋆ with overwhelming probability as soon as n ≥ S(Z ⋆ , Ω). In addition Amelunxen et al. (2013, Theorem II) show that a phase transition occurs at n = S(Z ⋆ , Ω) between a situation where recovery fails with large probability (for n ≤ S(Z ⋆ , Ω)γ √ m 1 m 2 , for some γ > 0) to a situation where recovery works with large probability (for n ≥ S(Z ⋆ , Ω) + γ √ m 1 m 2 ).

• Robust recovery with random measurements. Suppose we observe y = X (Z ⋆ ) + ǫ where X is again a random linear map, and in addition the observation is corrupted by a random noise ǫ ∈ R n . If the noise is bounded as ǫ 2 ≤ δ, then Chandrasekaran et al. (2012, Corollary 3.3) show that

Ẑ = arg min Z Ω(Z) s.th. X (Z) -y 2 ≤ δ (29) satisfies Ẑ -Z ⋆ Fro ≤ 2δ/η with overwhelming probability as soon as n ≥ (S(Z ⋆ , Ω) + 3 2 )/(1 -η) 2 . • Denoising. Assume a collection of noisy observations X i = Z ⋆ + σǫ i for i = 1, • • • , n is available where ǫ i ∈ R m 1 ×m 2 has i.i.d. N (0, 1)
entries, and let Y = 1 n n i=1 X i denote their average. Chandrasekaran and Jordan (2013, Proposition 4) prove that

Ẑ = arg min Z Z -Y Fro s.th. Ω(Z) ≤ Ω(Z ⋆ ) (30) satisfies E Ẑ -Z ⋆ 2 Fro ≤ σ 2 n S(Z ⋆ , Ω). • Demixing. Given two matrices Z ⋆ , V ⋆ ∈ R m 1 ×m 2 , suppose we observe y = U (Z ⋆ ) + V ⋆ where U : R m 1 ×m 2 → R m 1 ×m 2 is a random orthogonal operator. Given two convex functions Γ, Ω : R m 1 ×m 2 → R, Amelunxen et al. (2013, Theorem III) show that ( Ẑ, V ) = arg min (Z,V ) Ω(Z) s.th. Γ(V ) ≤ Γ(V ⋆ ) and y = U (Z) + V is equal to (Z ⋆ , V ⋆ ) with probability at least 1 -η provided that S(Z ⋆ , Ω) + S(V ⋆ , Γ) ≤ m 1 m 2 -4 m 1 m 2 log 4 η . Conversely if S(Z ⋆ , Ω) + S(V ⋆ , Γ) ≥ m 1 m 2 + 4 m 1 m 2 log 4
η , the demixing fails with probability at least 1η.

Some cone inclusions and their consequences

In this and subsequent sections, we wish to compare the behavior of Ω k,q and Ω k,q and Γ µ , as defined in (25). Before estimating and comparing the statistical dimensions of these norms, which requires rather technical proofs, let us first show through simple geometric arguments that for a number of matrices, the tangent cones of the different norms are actually nested. This will allow us to derive deterministic improvement in performance when a norm is used as regularizer instead of another, which should be contrasted with the kind of guarantees that will be derived from bounds on the statistical dimension and which are typically statements holding with very high probability. The results in this section are proved in Appendix C.

Proposition 18

The norms considered satisfy the following equalities and inequalities:

∀µ ∈ [0, 1], ∀Z ∈ R m 1 ×m 2 , Γ µ (Z) ≤ Ω k,q (Z) ≤ Ω k,q (Z), ∀µ ∈ [0, 1], ∀A ∈ A k,q , Γ µ (A) = Ω k,q (A) = Ω k,q (A) = 1.
Put informally, the unit balls of Ω k,q , Ω k,q and of all convex combinations of the trace norm and the scaled ℓ 1 -norm are nested and meet for matrices in A k,q . This property is illustrated in the vector case (for µ = 1) on Figure 1. In fact A k,q is a subset of the extreme points of the unit norms of all those norms except for the scaled ℓ 1 -norm (corresponding to the case µ = 1). Given that the unit balls meet on A k,q and are nested, their tangent cones on A k,q must also be nested:

Corollary 19
The following nested inclusions of tangent cones hold:

∀µ ∈ [0, 1], ∀A ∈ A k,q , T Γµ (A) ⊃ T Ω k,q (A) ⊃ T Ω k,q (A) . ( 31
)
As a consequence, for any A ∈ A k,q , the statistical dimensions of the different norms satisfy:

S(A, Ω k,q ) ≤ S(A, Ω k,q ) ≤ S(A, Γ µ ) . ( 32
)
As reviewed in Section 4.2.1, statistical dimensions provide estimates for the performance of the different norms in different contexts. Plugging (32) in these results shows that to estimate an atom in A k,q , using Ω k,q is at least as good as using Ω k,q which itself is at least as good as using any convex combination of the ℓ 1 and trace norms.

Note that the various statements in Section 4.2.1 provide upper bounds on the performance of the different norms, with are guarantees that are either probabilistic or hold in expectation. In fact, the inclusion of the tangent cones (31) and a fortiori the tangential inclusion of the unit balls imply much stronger results since it can also lead some deterministic statements, such as the following:

Corollary 20 (Improvement in exact recovery) Consider the problem of exact recovery of a matrix Z * ∈ A k,q from random measurements y = X (Z * ) by solving (28) with the different norms.

For any realization of the random measurements, exact recovery with Γ µ for any 0 ≤ µ ≤ 1 implies exact recovery with Ω k,q which itself implies exact recovery with Ω k,q .

Note that in the vector case (m 2 = 1), where the (k, q)-trace norm Ω k,1 boils down to the k-support norm θ k , the tangent cone inclusion (31) is not always strict:

Proposition 21 For any a ∈ A m k , T Γ 1 (a) = T θ k (a).
In words, the tangent cone of the ℓ 1 norm and of the the k-support norm are equal on k-sparse vectors with constant non-zero entries, which can be observed in Figure 1. This suggests that, in the vector case, the k-support norm is not better than the ℓ 1 norm to recover such constant sparse k-vectors.

Bounds on the statistical dimensions

The results presented in Section 4.2.2 apply only to a very specific set of matrices ( A k,q ), and do not characterize quantitatively the relative performance of the different norms. In this Section, we turn to more explicit estimations of the statistical dimension of the different norms at atoms in A k,q and A k,q . We consider first the statistical dimension of the (k, q)-CUT norm Ω k,q on its atoms A k,q . The unit ball of Ω k,q is a vertex-transitive polytope with 2 k+q m 1 k m 2 q vertices. As a consequence, it follows immediately from Corollary 3.14 in [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF] and from the upper bound

log m k ≤ k(1 + log(m/k)), that 6 Matrix norm S k = √ m Vector norm S (k, q)-trace O((k ∨ q) log (m 1 ∨ m 2 )) O( √ m log m) k-support Θ(k log p k ) (k, q)-cut O(k log m 1 k + q log m 2 q ) O( √ m log m) κ k Θ(k log p k ) ℓ 1 Θ(kq log m 1 m 2 kq ) Θ(m log m) ℓ 1 Θ(k log p k ) trace-norm Θ(m 1 + m 2 ) Θ(m) ℓ 2 p ℓ 1 + trace-n. Ω kq ∧ (m 1 + m 2 ) Θ(m) elastic net Θ(k log p k ) "cut-norm" O(m 1 + m 2 ) O(m) ℓ ∞ p
Table 2: Order of magnitude of the statistical dimension of different matrix norms for elements of A k,q (left) and of their vector norms counterpart for elements of A p k (right). The ℓ 1 norm here is the element-wise ℓ 1 norm. The column "k = √ m" corresponds to the case of the planted clique problem where m = m 1 = m 2 and k = q = √ m. We use usual Landau notation with f = Θ(g) for

(f = O(g))&(g = O(f )) and f = Ω(g) for g = O(f ).
The absence of Landau notation means that the computation is exact.

Proposition 22 For any A ∈ A k,q , we have

S(A, Ω k,q ) ≤ 16(k + q) + 9 k log m 1 k + q log m 2 q .
Upper bounding the statistical dimension of the (k, q)-trace norm on its atoms A k,q requires more work. First, atoms with very small coefficients are likely to be more difficult to estimate than atoms with large coefficients only. In the vector case, for example, it is known that the recovery of a sparse vector β with support I 0 depends on its smallest coefficient β min = min i∈I 0 β 2 i [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting[END_REF]. The ratio between β min and the noise level can be thought of as the worst signal-to-noise ratio for the signal β. We generalize this idea to atoms in A k,q as follows.

Definition 23 (Atom strength) Let A = ab ⊤ ∈ A k,q with I 0 = supp(a) and J 0 = supp(b). Denote a 2 min = min i∈I 0 a 2 i and b 2 min = min j∈J 0 b 2 j . The atom strength γ(a, b)

∈ (0, 1] is γ(a, b) := (k a 2 min ) ∧ (q b 2 min ).
Note that the atoms with maximal strength value 1 are the elements of A k,q . With this notion in hand we can now formulate an upper bound on the statistical dimension of Ω k,q :

Proposition 24 For A = ab ⊤ ∈ A k,q with strength γ = γ(a, b), we have

S(A, Ω k,q ) ≤ 322 γ 2 (k + q + 1) + 160 γ (k ∨ q) log (m 1 ∨ m 2 ) . ( 33
)
Note that the upper bounds obtained on atoms of A k,q for Ω k,q (Proposition 22) and Ω k,q (Proposition 24, with γ = 1) have the same rate up to k log k + q log q which is negligible compared to k log m 1 + q log m 2 when k ≪ m 1 and q ≪ m 2 . Note that once the support is specified, the number of degrees of freedom for elements of A k,q is k + q -1, which is matched up to logarithmic terms.

It is interesting to compare these estimates to the statistical dimension of the ℓ 1 norm, the trace norm, and their combinations Γ µ . Table 2 summarizes the main results. The statistical dimension the ℓ 1 norm on atoms in A k,q is of order kq log(m 1 m 2 /(kq)), which is worse than the statistical dimensions of Ω k,q and Ω k,q by a factor k ∧ q. On A k,q , though, the statistical dimension of Ω k,q increases when the atom strength decreases, while the statistical dimension of the ℓ 1 norm is independent of it and even decreases when the size of the support decreases. As for the trace norm alone, its statistical dimension is at least of order m 1 + m 2 , which is unsurprisingly much worse that the statistical dimensions of Ω k,q and Ω k,q since it does not exploit the sparsity of the atoms. Finally, regarding the combination Γ µ of the ℓ 1 norm and of the trace norm, [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF] has shown that it does not improve rates up to constants over the best of the two norms. More precisely, we can derive from Oymak et al. (2012, Theorem 3.

2) the following result

Proposition 25 There exists M > 0 and C > 0 such that for any m 1 , m 2 , k, q ≥ M with m 1 /k ≥ M and m 2 /q ≥ M , for any A ∈ A k,q and for any µ ∈ [0, 1], the following holds:

S (A, Γ µ ) ≥ C ζ(a, b) (kq) ∧ (m 1 + m 2 -1) -2 , with ζ(a, b) = 1 -1 - a 2 1 k 1 - b 2 1 q . Note that ζ(a, b) ≤ 1 with equality if either a ∈ A m 1 k or b ∈ A m 2 q , so in particular ζ(a, b) = 1 for ab ⊤ ∈ A k,q .
In that case, we see that, as stated by [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF], Γ µ does not bring any improvement over the ℓ 1 and trace norms taken imdividually, and in particular has a worse statistical dimension than Ω k,q and Ω k,q .

The vector case

We have seen in Section 4.2.3 that the statistical dimension of the (k, q)-trace norm and of the (k, q)-CUT norm were smaller than that of the ℓ 1 and the trace norms, and of their combinations, meaning that theoretically they are more efficient regularizers to recover rank-one sparse matrices. In this section, we look more precisely at these properties in the vector case (m 2 = q = 1), and show that, surprisingly, the benefits are lost in this case. Remember that, in the vector case, Ω k,q boils down to the k-support norm θ k (14), while Ω k,q boils down to the norm κ k (13). For the later, we can upper bound the statistical dimension at a k-sparse vector by specializing Proposition 22 to the vector case, and also derive a specific lower bound as follows:

Proposition 26 For any k-sparse vector a ∈ A p k , k 2π log p -k k + 1 ≤ S(a, κ k ) ≤ 9k log p k + 16(k + 1) .
From the explicit formulation of θ k (14) we can derive an upper bound of the statistical dimension of θ k on any sparse vector with at least k non-zero coefficients:

Proposition 27 For any s ≥ k, the statistical dimension of the k-support norm θ k at an s-sparse vector w ∈ R p is bounded by

S(w, θ k ) ≤ 5 4 s + 2 (r + 1) 2 wI 2 2 2 wI 1 2 1 + |I 1 | log p s , (34)
where w ∈ R p denotes the vector with the same entries as w sorted by decreasing absolute values, r is as defined in equation ( 14),

I 2 = [1, k -r -1] and I 1 = [k -r, s].
In particular, when s = k, the following holds for any atom a ∈ A p k with strength γ = ka 2 min :

S(a, θ k ) ≤ 5 4 k + 2k γ log p k . ( 35
)
We note that (35) has the same rate but tighter constants than the general upper bound (33) specialized to the vector case. In particular, this suggests that the γ -2 term in (35) may not be required. In the lasso case (k = 1), we recover the standard bound [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]:

S(w, θ k ) ≤ 5 4 s + 2s log p s , (36)
which is also reached by θ k on an atom a ∈ A p k because in that case γ = 1 in (35). On the other hand, for general atoms in A p k the upper bound ( 35) is always worse than the upper bound for the standard Lasso (36), and more generally the upper bound for general sparse vectors (34) is also never better than the one for the Lasso. Although these are only upper bounds, this raises questions on the utility of the k-support norm compared to the lasso to recover sparse vectors. The statistical complexities of the different regularizers in the vector case are summarized in Table 2. We note that, contrary to the low-rank sparse matrix case, the ℓ 1 -norm, the k-support norm, and the norm κ k all have the same statistical dimension up to constants. Note that the tangent cone of the elastic net equals the tangent cone of the ℓ 1 -norm in any point (because the tangent cone of the ℓ 2 norm is a half space that always contains the tangent cone of the ℓ 1 -norm) so that the elastic net has always the exact same statistical dimension as the ℓ 1 -norm.

Algorithms

As seen in Section 3, many problems involving sparse low-rank matrix estimation can be formulated as optimization problems of the form:

min Z∈R m 1 ×m 2 L(Z) + λΩ k,q (Z). (37)
Unfortunately, although convex, this problem may be computationally challenging (Section 3.5). In this section, we present a working set algorithm to approximately solve such problems in practice when L is differentiable.

A working set algorithm

Given a set S ⊂ G m 1 k × G m 2 q
of pairs of row and column subsets, let us consider the optimization problem:

min (Z (IJ ) ) (I,J )∈S    L (I,J)∈S Z (IJ ) + λ (I,J)∈S Z (IJ ) * : ∀(I, J) ∈ S, supp(Z (IJ ) ) ⊂ I × J    . (P S )
Let ( Z (IJ ) ) (I,J)∈S be a solution of this optimization problem. Then, by the characterization of ) is the solution of (37

Ω k,q (Z) in (8), Z = (I,J)∈S Z (IJ
) when S = G m 1 k × G m 2 q .
Clearly, it is still the solution of (37) if S is reduced to the set of non-zero matrices Z (IJ ) at optimality often called active components. We propose to solve problem (37) using a so-called working set algorithm which solves a sequence of problems of the form (P S ) for a growing sequence of working sets S, so as to keep a small number of non-zero matrices Z (IJ ) throughout. Working set algorithms (Bach et al., 2011, Chap. 6) are typically useful to speed up algorithm for sparsity inducing regularizer; they have been used notably in the case of the overlapping group Lasso of [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF] which is also naturally formulated via latent components.

To derive the algorithm we write the optimality condition for (P S ):

∀(I, J) ∈ S , ∇L(Z) IJ ∈ -λ∂ Z (IJ) * .
From the characterization of the subdifferential of the trace norm [START_REF] Curran Associates | Characterization of the subdifferential of some matrix norms[END_REF], writing Z (IJ ) = U (IJ ) Σ (IJ ) V (IJ ) the SVD of Z (IJ ) , this is equivalent to, for all (I, J) in S, either Z (IJ ) = 0 and ∇L(Z

) IJ = -λ U (IJ ) V (IJ ) ⊤ + A with A op ≤ 1 and AU (IJ ) = A ⊤ V (IJ ) = 0 , (38)
or

Z (IJ ) = 0 and ∇L(Z)] IJ op ≤ λ . ( 39
)
The principle of the working set algorithm is to solve problem (P S ) for the current set S so that ( 38) and ( 39) are (approximately) satisfied for (I, J) in S, and to check subsequently if there are any components not in S which violate (39). If not, this guarantees that we have found a solution to problem (37), otherwise the new pair (I, J) corresponding to the most violated constraint is added to S and problem (P S ) is initialized with the previous solution and solved again. The resulting algorithm is Algorithm 1 (where the routine SSVDTPI is described in the next section). Problem (P S ) is solved easily using the approximate block coordinate descent of [START_REF] Tseng | A coordinate gradient descent method for nonsmooth separable minimization[END_REF] (see also Bach et al., 2011, Chap. 4), which consists in iterating proximal operators. The modifications to the algorithm to solve problems regularized by the norm Ω k, are relatively minor (they amount to replace the trace norms by penalization of the trace of the matrices Z (IJ ) and by positive definite cone constraints) and we therefore do not describe them here. Determining efficiently which pair (I, J) possibly violates condition ( 39) is in contrast a more difficult problem that we discuss next.

Algorithm 1 Active set algorithm Require: L, tolerance ǫ > 0, parameters λ, k, q Set S = ∅, Z = 0 while c = true do Recompute optimal values of Z, (Z (IJ ) ) (I,J)∈S for (P S ) using warm start

(I, J) ← SSVDTPI(∇L(Z), k, q, ǫ) if [∇L(Z)] I,J op > λ then S ← S ∪ {(I, J)} else c ← false end if end while return Z, S, (Z (IJ ) ) (I,J)∈S

Finding new active components

Once (P S ) is solved for a given set S, (38) and (39) are satisfied for all (I, J) ∈ S. Note that (38) implies in particular that ∇L(Z)] IJ op = λ when Z (IJ ) = 0 at optimality. Therefore, (39) is also satisfied for all (I, J) / ∈ S if and only if

max (I,J)∈G m 1 k ×G m 2 q [∇L(Z)] IJ op ≤ λ , (40)
and if this is not the case then any (I, J) that violates this condition is a candidate to be included in S. This corresponds to solving the following sparse singular value problem

max a,b a ⊤ ∇L(Z)b s.t. ab ⊤ ∈ A k,q . (k, q)-linRank-1
This problem is unfortunately NP-hard since rank 1 sparse PCA problem is a particular instance of it (when ∇L(Z) is replaced by a covariance matrix), and we therefore cannot hope to solve it exactly with efficient algorithms. Still, sparse PCA has been the object of a significant amount of research, and several relaxations and other heuristics have been proposed to solve it approximately. In our numerical experiments we use a truncated power iteration (TPI) method, also called TPower, GPower or CongradU in the PSD case [START_REF] Journée | Generalized power method for sparse principal component analysis[END_REF][START_REF] Luss | Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint[END_REF][START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF], which has been proved recently by [START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF] to provide accurate solution in reasonable computational time under RIP type of conditions. Algorithm 2 provides a natural generalization of this algorithm to the non-PSD case. The algorithm follows the steps of a power method, the standard method for computing leading singular vectors of a matrix, with the difference that at each iteration a truncation step is use. We denote the truncation operator by T k . It consists of keeping the k largest components (in absolute value) and setting the others to 0. Note that Algorithm 2 may fail to find a new active component for Algorithm 1 if it Algorithm 2 SSVDTPI: Bi-truncated power iteration for (k, q)-linRank-1 Require: A ∈ R m 1 ×m 2 , k, q and tolerance ǫ > 0 Pick a random initial point b (0) ∼ N (0, I m 2 ) and let while |a

(t)⊤ Ab (t) -a (t-1)⊤ Ab (t-1) |/|a (t-1) ⊤ Ab (t-1) | > ǫ do a ← Ab (t) \\ Power a ← T k (a) \\ Truncate b ← A ⊤ a \\ Power b ← T q (b) \\ Truncate a (t+1)
← a/ a 2 and b (t+1) ← b/ b 2 \\ Normalize t ← t + 1 end while I ← Supp(a (t) ) and J ← Supp(b (t) ) return (I, J) finds a local maximum of ((k, q)-linRank-1) smaller than λ, and therefore result in the termination of Algorithm 1 on a suboptimal solution. On the positive side, note that Algorithm 1 is robust to some errors of Algorithm 2. For instance, if an incorrect component is added to S at some iteration, but the correct components are identified later, Algorithm 1 will eventually shrink the incorrect components to 0. One of the causes of failure of TPI type of methods is the presence of a large local maximum in the sparse PCA problem corresponding to a suboptimal component; incorporating this component in S will reduce the size of that local maximum, thereby increasing the chance of selecting a correct component the next time around.

Computational cost

Note that when m 1 , m 2 are large, solving P S involves the minimizations of trace norms of matrices of size k × q which, when k and q are small compared to m 1 and m 2 have low computational cost. The bottleneck for providing a computational complexity of the algorithm is the (k, q)-linRank-1 step. It has been proved by [START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF] that under some conditions the problem can be solved in linear time. If the conditions hold at every step of gradient, the overall cost of an iteration can be cast into the cost of evaluating the gradient and the evaluation of thin SVDs: O(k 2 q). Evaluating the gradient has a cost dependent on the risk function L. This cost for usual applications is O(m 1 m 2 ). So assuming the RIP conditions required by [START_REF] Yuan | Truncated power method for sparse eigenvalue problems[END_REF] hold, the cost of Algorithm 2 is dominated by matrix-vector multiplications so of the order O(m 1 m 2 ). The total cost of the algorithm for reaching a δ-accurate solution is therefore O((m 1 m 2 + k 2 q)/δ). However the worst case complexity of the algorithm is non-polynomial as (k, q)-linRank-1 is nonpolynomial in general. We would like to point out that in our numerical experiments a warm start with singular vectors and multiple runs of the algorithm (k, q)-linRank-1 keeping track of the highest found variance has provided us a very fast and reliable solver. Further discussion on this step go beyond the scope of this work.

Numerical experiments

In this section we report experimental results to assess the performance of sparse low-rank matrix estimation using different techniques. We start in Section 6.1 with simulations aiming at validating the theoretical results on statistical dimension of Ω k,q and assessing how they generalize to matrices with (k, q)-rank larger than 1. In Section 6.2 we compare several techniques for sparse PCA on simulated data.

Empirical estimates of the statistical dimension.

In order to numerically estimate the statistical dimension S(Z, Ω) of a regularizer Ω at a matrix Z, we add to Z a random Gaussian noise matrix and observe Y = Z + σG where G has normal i.i.d. entries following N (0, 1). We then denoise Y using (30) to form an estimate Ẑ of Z. For small σ, the normalized mean-squared error (NMSE) defined as

NMSE(σ) := E Ẑ -Z 2 Fro σ 2
is a good estimate of the statistical dimension, since Oymak and Hassibi (2013) show that

S(Z, Ω) = lim σ→0 NMSE(σ) .
Numerically, we therefore estimate S(Z, Ω) by taking σ = 10 -4 and measuring the empirical NMSE averaged over 20 repeats. We consider square matrices with m 1 = m 2 = 1000, and estimate the statistical dimension of Ω k,q , the ℓ 1 and the trace norms at different matrices Z. The constrained denoiser (30) has a simple close-form for the ℓ 1 and the trace norm. For Ω k,q , it can be obtained by a series of proximal projections (15) with different parameters λ until Ω k,q ( Ẑ) has the correct value Ω k,q (Z). Since the noise is small, we found that it was sufficient and faster to perform a (k, q)-SVD of Y by solving (15) with a small λ, and then apply the ℓ 1 constrained denoiser to the set of (k, q)-sparse singular values. We first estimate the statistical dimensions of the three norms at an atom Z ∈ A k,q , for different values of k = q. Figure 2 (top left) shows the results, which confirm the theoretical bounds summarized in Table 2. The statistical dimension of the trace norm does not depend on k, while that of the ℓ 1 norm increases almost quadratically with k and that of Ω k,q increases linearly with k. As expected, Ω k,q interpolates between the ℓ 1 norm (for k = 1) and the trace norm (for k = m 1 ), and outperforms both norms for intermediary values of k. This experiments therefore confirms that our upper bound (33) on S(Z, Ω k,q ) captures the correct order in k, although the constants can certainly be much improved, and that Algorithm 1 manages, in this simple setting, to correctly approximate the solution of the convex minimization problem. Second, we estimate the statistical dimension of Ω k,q on matrices with (k, q)-rank larger than 1, a setting for which we proved no theoretical result. Figure 2 (top left) shows the numerical estimate of S(Z, Ω k,q ) for matrices Z which are sums of r atoms in A k,k with non-overlapping support, for k = 10 and varying r. We observe that the increase in statistical dimension is roughly linear in the (k, q)-rank. For a fixed (k, q)-rank of 3, the bottom plots of Figure 2 compare the estimated statistical dimensions of the three regularizers on matrices Z which are sums of 3 atoms in A k,k with non-overlapping (bottom left) or overlapping (bottom right) supports. The shapes of the different curves are overall similar to the rank 1 case, although the performance of Ω k,q degrades as the supports of atoms overlap. In both cases, Ω k,q consistently outperforms the two other norms.

Overall these experiments suggest that the statistical dimension of Ω k,q at a linear combination of r atoms increases as Cr (k log m 1 + q log m 2 ) where the coefficient C increases with the overlap among the supports of the atoms.

Comparison of algorithms for sparse PCA

In this section we compare the performance of different algorithms in estimating a sparsely factored covariance matrix that we denote Σ ⋆ . The observed sample consists of n random vector vectors generated i.i.d. according to N (0, Σ ⋆ + σ 2 Id p ), where (k, k)-rank(Σ ⋆ ) = 3. The matrix Σ ⋆ is formed by adding 3 blocks of rank 1,

Σ ⋆ = a 1 a ⊤ 1 + a 2 a ⊤ 2 + a 3 a ⊤ 3
, having all the same sparsity a i 0 = k = 10, 3×3 overlaps and nonzero entries equal to 1/ √ k. See Figure 3, bottom right plot for a representation of the ground truth Σ ⋆ . The noise level σ = 0.8 is set in order to make the signal to noise ratio below the level σ = 1 where a spectral gap appears and makes the spectral baseline (penalizing the trace of the PSD matrix) work. In our experiments the number of variables is p = 200 and n = 80 points are observed. To estimate the true covariance matrix from the noisy observation, first the sample covariance matrix is formed as

Σn = 1 n n i=1 x i x ⊤ i ,
and given as input to various algorithms which provide a new estimate Σ. The methods we compared are the following:

• Raw sample covariance. The most basic is to output Σn as the estimate of the covariance, which is not accurate due to presence of noise and underdeterminedness n < p.

• Trace penalty on the PSD cone. This spectral algorithm solves the following optimization problem in the cone of PSD matrices:

min Z 0 1 2 Z -Σn 2 Fro + λ Tr Z .
• ℓ 1 penalty. In order to approximate the sample covariance Σn by a sparse matrix a basic idea is to soft-threshold it element-by-element. This is equivalent to solving the following convex optimization problem: Other plots contain heatmaps of the estimated covariance matrix using different methods, and the ground truth Σ ⋆ in the lower right hand side.

min Z 1 2 Z -Σn 2 Fro + λ Z 1 .

Sample covariance

Trace ℓ 1 Trace + ℓ 1 Sequential Ω k, 4.20 ± 0.02 0.98 ± 0.01 2.07 ± 0.01 0.96 ± 0.01 0.93 ± 0.08 0.59 ± 0.03

Table 3: Relative error of covariance estimation with different methods.

• Trace + ℓ 1 penalty. The restriction of Γ µ to the PSD cone, which is equivalent to solving the following SDP

min Z 0 1 2 Z -Σn 2 Fro + λΓ µ (Z) .
This approach needs to tune two parameters λ > 0, µ ∈ [0, 1].

• Sequential sparse PCA. This is the standard way of estimating multiple sparse principal components which consists of solving the problem for a single component at each step t = 1 • • • r, and deflate to switch to the next (t + 1)st component. The deflation step used in this algorithm is the orthogonal projection

Z t+1 = (Id p -u t u ⊤ t ) Z t (Id p -u t u ⊤ t ) .
The tuning parameters for this approach are the sparsity level k and the number of principal components r.

• Ω k, penalty. The following optimization problem, which is a proximal operator computation, is solved using the active set algorithm:

min Z 0 1 2 Z -Σn 2 Fro + λΩ k, (Z) ,
with Ω k, the gauge associated with A k,≻ already introduced in Section 3.4. The two parameters of this method are λ > 0 and k ∈ N\{0}.

We report the relative errors Σ -Σ ⋆ Fro / Σ ⋆ Fro over 10 runs of our experiments in Table 3, and a representation of the estimated matrices can be found in Figure 3. We observe that sparse PCA methods using Ω k, and also the sequential method using deflation steps outperform spectral and ℓ 1 baselines. In addition, penalizing Ω k, is superior to the sequential approach. This was expected since our algorithm minimizes a loss function that is close to the test errors reported, whereas the sequential scheme does not optimize a well-defined objective.

Conclusion

In this work, we proposed two new convex penalties, the (k, q)-trace norm and the (k, q)-CUT norm, specifically tailored to the estimation of low-rank matrices with sparse factors. Our motivation for proposing such convex formulations for sparse low-rank matrix inference was twofold. First, it allowed us to consider algorithmic schemes that are better understood when a problem is formulated as a convex optimization problem, even though the complexity of solving the problem exactly remains super-polynomial. Second, using convex geometry allowed us to provide sample complexity and statistical guarantees, and notably to show that the proposed estimators have much better statistical dimension than more standard convex combinations of the ℓ 1 and trace norms. We observed that the improvement exists only for matrices: for sparse vectors, using our penalty (which boils down to the k-support norm in this case) does not improve over the standard ℓ 1 norm, in terms of statistical dimension increase rate. One limitation of this work is that we assume that the sparsity of the factors is known and fixed. Lifting this constraint and investigating procedures that can adapt to the size of the blocks (like the ℓ 1 norm adapts to the size of the support) is an interesting direction for future research. Another interesting direction is to use the nuclear norm formulation of the (k, q)-trace norm as in Lemma 10 to optimize the regularized problem.

A Proofs of results in Sections 2 and 3.

Proof [Proposition 2]

To prove the first claim, note that a matrix of the form ab ⊤ for a ∈ A m 1 k and b ∈ A m 2 q has at most kq non-zero terms. Therefore, the decomposition of a matrix with no null entries as a linear combination of such sparse matrices must count at least m 1 m 2 kq terms, which is larger than m 1 ∨ m 2 when kq ≤ m 1 ∧ m 2 . To prove second claim, consider for the matrix Z = 11 ⊤ ∈ R 3 the problem of finding a decomposition of Z which attains the (2, 2)-rank. It is impossible to write Z as the sum of two (2, 2)-sparse matrices, because it would then have at most 8 non-zero coefficients. But we have the decomposition.

1 1 1 1 1 1 1 1 1 = 2 1 0 1 1 2 0 0 0 0 + 0 0 1 0 1 2 1 0 1 2 - 1 0 -1 0 0 0 -1 0 1
, which shows that the (2, 2)-rank of Z is 3. Note that this decomposition is not unique: given that Z is invariant by any of the 6 permutations of the rows and any of the 6 permutations of the columns, Z admits at least 36 different decompositions attaining the (2, 2)-rank. Now, observe that the decomposition proposed above for Z = 11 ⊤ ∈ R 3 yields 3 left-and right-(2, 2)-sparse factors that are obviously not orthogonal. It can actually be shown by systematic enumeration of all possible cases that it is impossible to find any (2, 2)-sparse decomposition of Z with left or right factors that are orthogonal.

Proof [Proposition 6]

To prove the first claim, let us consider the matrix Z = 11 ⊤ ∈ R 3 . We showed in the proof of Proposition 2 above that its (2, 2)-rank is equal to 3. We now show that the number of its (k, q)sparse singular value is 9, and thus much larger than 3. For that purpose, we express any (2, 2)-SVD of Z as a minimizer of (8), and write the corresponding Lagrangian:

L((Z (IJ ) ) I,J , K) = I,J∈G 2 Z (IJ ) * + tr K ⊤ Z - I,J∈G 2 Z (IJ ) ,
where (Z (IJ ) ) I,J and K are the primal and dual variables. It is easy to check that the dual solution is the unique subgradient of Ω 2,2 at Z which is equal to K * = 1 2 Z. But any primal solution must satisfy tr(K * ⊤ Z (IJ ) ) = Z (IJ ) * . This implies that any primal solution (Z (IJ ) ) I,J satisfies Z (IJ ) ∝ 1 I 1 ⊤ J . Then, one can check that (( 12 )1 I 1 ⊤ J ) I,J∈G 2 forms a basis of R 3×3 so that any matrix Z admits a unique set of decomposition coefficients on that basis. This proves that the unique solution of ( 8) is the one such that Z (IJ ) = 1 4 1 I 1 ⊤ J for all pairs (I, J) ∈ G 2 × G 2 . This unique (k, q)-SVD is composed of 9 terms which is strictly larger than its (k, q)-rank, the latter being equal to 3. To prove the second claim, let us consider the (2, 2)-SVDs of Z = 1 2 11 ⊤ ∈ R 4 . By proposition 18,

1 2 Z 1 ≤ Ω 2,2 (Z), but 1 2 Z 1 = 4 and 2Z = (1 {1,2} + 1 {3,4} )(1 {1,2} + 1 {3,4} ) ⊤ which shows that Ω 2,2 (Z) ≤ 4. So Ω 2,2 (Z) = 4.
Considering that there are 3 ways to partition {1, 2, 3, 4} into sets of cardinality 2, Z admits at least 9 different optimal decompositions in the sense of the (2, 2)-SVD since Z can be written in 9 different ways as the sum of four matrices of A 2,2 with disjoint supports. Each of these decompositions attains the (2, 2)-rank which is equal to 4. Note also that by convexity any convex combination of these decompositions is also an optimal decomposition in the sense of the (2, 2)-SVD, but can contain up to 36 terms! To prove the third claim, let us consider

Z 1 = 1 1 0 1 1 0 0 0 0 , Z 2 = 0 0 0 0 1 1 0 1 1 , Z = Z 1 + Z 2 = 1 1 0 1 2 1 0 1 1 .
As Z 1 , Z 2 , Z are all positive semidefinite we have Z 1 * = 2, Z 2 * = 2, and Z * = 4. By inequality (7), Ω 2,2 (Z) ≥ Z * = 4 which proves that the decomposition

Z = Z 1 + Z 2 is optimal: Ω 2,2 (Z) = 4. But Z 1 , Z 2 = 1. So this decomposition is a decomposition of Z onto linear combi- nation of atoms 1 2 Z 1 , 1 2 Z 2 ∈ A 2,2 which are not orthogonal. Proof [Lemma 7]
We first show (9) from the definition of the dual norm Ω * k,q :

Ω * k,q (Z) = max K { K, Z : Ω k,q (K) ≤ 1} = max a,b { Z, ab ⊤ : ab ⊤ ∈ A k,q } = max a,b {a ⊤ Zb : a 0 ≤ k , b 0 ≤ q , a 2 = b 2 = 1} = max I,J Z I,J op : I ∈ G m 1 k , J ∈ G m 2 q ,
where the second equality follows from the fact that the maximization of a linear form over a bounded convex set is attained at one of the extreme points of the set. Given this closed-form expression of the dual norm, we prove the variational formulation (8) for the primal norm Ω k,q . Consider the function Ω k,q defined by

Ω k,q (Z) = inf    (I,J)∈G m 1 k ×G m 2 q Z (I,J) * : Z = (I,J) Z (I,J) , supp(Z (I,J) ) ⊂ I × J    .
Since Ω k,q (Z) is defined as the infimum of a jointly convex function of Z and (Z (I,J)

) I∈G m 1 k , J∈G m 2 q
obtained by minimizing w.r.t. to the latter variables, it is a an elementary fact from convex analysis that Ω k,q is a convex function of Z. It is also symmetric and positively homogeneous, which together with convexity prove that Ω k,q defines a norm. We can compute its dual norm as

Ω k,q * (K) = max Z K, Z : Ω k,q (Z) ≤ 1 = max (Z (IJ ) ) (I,J )    K, (I,J) Z (IJ ) : (I,J) Z (IJ ) * ≤ 1 , supp(Z (IJ ) ) ⊂ I × J    = max (Z (IJ ) ) (I,J ) ,(η (IJ ) ) (I,J )    (I,J) η (I,J) K I,J , Z (IJ ) : Z (IJ ) * ≤ η (IJ ) , (I,J) η (IJ ) ≤ 1    = max (η (IJ ) ) (I,J )    (I,J) η (IJ ) K I,J op : (I,J) η (IJ ) ≤ 1    = max (I,J) K I,J op = Ω * k,q (K) .
This proves that Ω k,q (K) = Ω k,q (K) since a norm is uniquely characterized by its dual norm. Finally, to show (10) we use the general characterization of the subdifferential of a norm (e.g., [START_REF] Curran Associates | Characterization of the subdifferential of some matrix norms[END_REF]:

G ∈ ∂Ω k,q (A) ⇔ Ω k,q (A) = G, A , Ω * k,q (G) ≤ 1 .
Let us denote a subgradient by G = A + Z. Since A = ab ⊤ is an atom, we have Ω k,q (A) = 1. In addition, A 2 Fro = Tr(ba ⊤ ab ⊤ ) = 1, therefore the condition Ω k,q (A) = G, A boils down to Z, A = 0. Given the characterization of the dual norm (9), we therefore get:

∂Ω k,q (A) = A + Z : A, Z = 0, ∀(I, J) ∈ G m 1 k × G m 2 q A I,J + Z I,J op ≤ 1 .

Let now

D(A) = A + Z : AZ ⊤ I 0 ,J 0 = 0, A ⊤ Z I 0 ,J 0 = 0, ∀(I, J) ∈ G m 1 k × G m 2 q A I,J + Z I,J op ≤ 1 . Since A, Z = A, Z I 0 ,J 0 = Tr (A ⊤ Z I 0 ,J 0 ), it is clear that D(A) ⊂ ∂Ω k,q (A). Conversely, let G = A+Z ∈ ∂Ω k,q (A). Then A, Z = ab ⊤ , Z I 0 ,J 0 = a ⊤ Z I 0 ,J 0 b = 0,
and therefore, by Pythagorean equality applied to the orthogonal vectors a and Z I 0 ,J 0 b:

(A I 0 ,J 0 + Z I 0 ,J 0 ) b 2 2 = ab ⊤ b + Z I 0 ,J 0 b 2 2 = a + Z I 0 ,J 0 b 2 2 = 1 + Z I 0 ,J 0 b 2 2 ,
but since A I 0 ,J 0 + Z I 0 ,J 0 op ≤ 1 and b 2 = 1 we must have Z I 0 ,J 0 b 2 = 0. This shows that AZ ⊤ I 0 ,J 0 = ab ⊤ Z ⊤ I 0 ,J 0 = 0. The same reasoning starting with the orthogonal vectors b and Z ⊤ I 0 ,J 0 a shows that we also have A ⊤ Z I 0 ,J 0 = 0, implying that ∂Ω k,q (A) ⊂ D(A). This concludes the proof that ∂Ω k,q (A) = D(A), as claimed in (10).

Proof [Lemma 10] Let ν be the nuclear norm induced by two atomic norms • α and • β , induced themselves respectively by the two atom sets A 1 and A 2 . Let A = ab ⊤ : a ∈ A 1 , b ∈ A 2 and B = Conv A , then the key argument is to note that we have

ab ⊤ : a α ≤ 1, b β ≤ 1 ⊂ B . Indeed, if a = i λ i a i and b = j λ ′ j b j with a i ∈ A 1 , b j ∈ A 2 and i λ i = j λ ′ j = 1, then with µ ij := λ i λ ′ j , we have ab ⊤ = i,j µ ij a i b ⊤ j and i,j µ ij = 1.
The inclusion is then proved by density. By (12) the dual norm of ν satisfies

ν * (Z) = sup a ⊤ Zb : a α ≤ 1 , b β ≤ 1 , so that ν * (Z) ≤ sup { Z, ab ⊤ : ab ⊤ ∈ B} = sup { Z, ab ⊤ : ab ⊤ ∈ A} ≤ ν * (Z) ,
where the middle equality is due to the fact that the maximum of a linear function on a convex set is attained at a vertex. We therefore have ν * (Z) = sup { Z, A : A ∈ A}. Given (4), this shows that ν is the atomic norm induced by A.

Proof [Theorem 11] Since the (k, q)-trace norm is the atomic norm induced by the atom set (5), Lemma 10 tells us that it is also the nuclear norm induced by the two atomic norms with atom sets A m 1 k and A m 2 q , which correspond exactly to the so-called k-and q-support norms of Argyriou et al. (2012). To prove the second statement, we proceed similarly to get that the (k, q)-CUT norm is the nuclear norm induced by the two atomic norms with atom sets A m 1 k and A m 2 k . Calling κ k and κ q these norms, we obtain an explicit formulation as follows:

κ k (w) = max s { s, w : κ * k (s) ≤ 1} = max s, w : 1 √ k k i=1 |s (i) | ≤ 1 =        1 k √ k w 1 if w 1 ≥ k w ∞ 1 √ k w ∞ if w 1 ≤ k w ∞ = 1 √ k max w ∞ , 1 k w 1 . Proof [Lemma 12]
The form of θ * k follows immediately from the fact that θ * k (w) = max{a ⊤ w : a ∈ A k }. Similarly for κ * k , we have

κ * k (s) = max a, s : a ∈ A k = max I:|I|=k s I 1 = 1 √ k k i=1 |s (i) |,
where s (i) denotes the the ith largest element of s in absolute value. This norm is proportional to a norm known as the vector k-norm or 1-k symmetric norm gauge.

Proof [Proposition 13]

To prove the first claim, we show a counterexample for the (2, 2)-SVD in R 4×4 . Let I = {1, 2} and J = {3, 4}. The matrix Z = 11 ⊤ ∈ R 4 can be written as Z = Z I,I + Z I,J + Z J,I + Z J,J , and so its (2, 2)-rank is less than 4. But its (2, 2)-rank must be at least 4, because the matrix has 16 non-zeros coefficients and the sum of three (2, 2)-sparse matrices has at most 12 non-zero coefficients. Its (2, 2)-rank is thus equal to 4. However, it is not possible to write it as a sum of less than 6 symmetric (2, 2)-sparse matrices, because each of these matrices can only make one coefficient above the non-diagonal non-zero.

For the second claim, we have shown in the proof of proposition 6 that the decomposition above is a (2, 2)-SVD.

To prove the third claim, note first that the case k = 1 is peculiar and not representative of the general case because the span of the PSD matrices of sparsity 1 are only the diagonal matrices, while the span of rank one PSD matrices of sparsity k × k for k > 1 is all the symmetric matrices. Now, we claim that it is not possible to write Z = 11 ⊤ ∈ R 3 as a sum of PSD matrices that are (2, 2)-sparse and PSD. Indeed, if this was the case, this would imply the existence of a non zero vector v with a support of size at most 2 such that Zvv ⊤ ≻ 0. Since the only eigenvector of Z associated with a non-zero eigenvalue is the constant vector this is impossible.

B Proofs of results in Section 4.1

Proof [Lemma 14]
We prove a more general result than Lemma 14. Let Ω : R m 1 ×m 2 → R be any matrix norm, and X : R m 1 ×m 2 → R n be a linear map. We denote by X i (i = 1, . . . , n) the i-th design matrix defined by X (Z) i = Z, X i . For a given matrix Z ⋆ ∈ R m 1 ×m 2 , assume we observe:

Y = X (Z ⋆ ) + ǫ , (41)
where ǫ ∈ R n is a centered random noise vector. We consider the following estimator of Z ⋆ :

ẐΩ ∈ arg min Z 1 2n Y -X (Z) 2 2 + λΩ(Z) , (42)
for some value of the parameter λ > 0. The following result generalizes standard results known for the ℓ 1 and trace norms (e.g., [START_REF] Koltchinskii | Nuclear norm penalization and optimal rates for noisy matrix completion[END_REF], Theorem 1) to any norm Ω.

Theorem 28 If λ ≥ 1 n Ω * ( n i=1 ǫ i X i ) then 1 2n X ( ẐΩ -Z ⋆ ) 2 2 ≤ inf Z 1 2n X (Z -Z ⋆ ) 2 2 + 2λΩ(Z) . ( 43
)
Lemma 14 is then a simple consequence of Theorem 28 by taking for X the identity map, upper bounding the right-hand side of ( 43) by the value 2λΩ(Z ⋆ ) it takes for Z = Z ⋆ , and replacing λ by λ/n.

Proof [Theorem 28] By definition of ẐΩ (42), we have for all Z:

1 2n Y -X ( ẐΩ ) 2 2 ≤ 1 2n Y -X (Z) 2 2 + λ Ω(Z) -Ω( ẐΩ ) ,
which after developing the squared norm and replacing Y by (41) gives

1 2n X ( ẐΩ ) 2 2 - 1 n X (Z ⋆ ) + ǫ, X ( ẐΩ ) ≤ 1 2n X (Z) 2 2 - 1 n X (Z ⋆ ) + ǫ, X (Z) + λ Ω(Z) -Ω( ẐΩ ) ,
and therefore

1 2n X ( ẐΩ -Z ⋆ ) 2 2 ≤ 1 2n X (Z -Z ⋆ ) 2 2 + 1 n ǫ, X ( ẐΩ -Z) + λ Ω(Z) -Ω( ẐΩ ) . (44)
Now, using the fact (true for any norm) that Ω(A)Ω ⋆ (B) ≥ A, B for any vectors A, B ∈ R n , and taking λ ≥ 1 n Ω * ( n i=1 ǫ i X i ), we can upper bound the second term of the right-hand side of (44) by:

1 n ǫ, X ( ẐΩ -Z) = 1 n n i=1 ǫ i X ( ẐΩ -Z) i = 1 n n i=1 ǫ i X i , ẐΩ -Z = 1 n n i=1 ǫ i X i , ẐΩ -Z ≤ 1 n Ω ⋆ n i=1 ǫ i X i Ω ẐΩ -Z ≤ λΩ ẐΩ -Z
Plugging this bound back in (44) finally gives

1 2n X ( ẐΩ -Z ⋆ ) 2 2 ≤ 1 2n X (Z -Z ⋆ ) 2 2 + λΩ( ẐΩ -Z) + λ Ω(Z) -Ω( ẐΩ ) ≤ 1 2n X (Z -Z ⋆ ) 2 2 + 2λΩ(Z) ,
the last inequality being due to the triangle inequality.

Before proving Propositon 15, let us first derive an intermediary results useful to obtain an upper bound on the dual (k, q)-trace norm of a random matrix with i.i.d. normal entries.

Lemma 29 Let G be a m 1 × m 2 random matrix with i.i.d. normally distributed entries. Then

E max I∈G k ,J∈Gq G I,J 2 op ≤ 16 k log m 1 k + q log m 2 q + 2(k + q) .
Proof [Lemma 29] For a random matrix H ∈ R k×q with i.i.d. standard normal entries, we have the following concentration inequality (e.g., [START_REF] Davidson | Local operator theory, random matrices and Banach spaces[END_REF]: for s ≥ 0,

P[ H op > √ k + √ q + s] ≤ exp(-s 2 /2) . (45)
Denoting R = 2 √ k + √ q , and f (x) = e tx 2 , we have the sequence of inequalities

E exp(t H 2 op ) = Ef ( H op ) = ∞ 1 P[f ( H op ) > h] dh ≤ 1+f (R) 1 1 dh + ∞ 1+f (R) P[f ( H op ) > h]dh = f (R) + ∞ 0 P[ H op > f -1 (f (R) + 1 + ζ)]dζ ≤ f (R) + ∞ 0 P[ H op > 1 2 R + 1 2 f -1 (1 + ζ)]dζ (46) ≤ f (R) + ∞ 0 8ts exp -s 2 /2 + 4ts 2 ds (47) ≤ f (R) + 4 t 1 2 -4t (48) ≤ exp(8t(k + q)) + 8t 1 -8t ,
where the change of variable used in ( 47) is 1 + ζ = f (2s) = e 4ts 2 , (48) is true for any t < 1 8 , and (46) follows from the property of the inverse f -1 (z) = log(z) t that it is strictly increasing on [1; ∞) and sandwiched via

1 2 f -1 (z) + f -1 (z ′ ) ≤ f -1 (z + z ′ ) ≤ f -1 (z) + f -1 (z ′ ) . (49)
Take now t = 1 8 -1 8(k+q) . Since k + q ≥ 2, we have 1/16 ≤ t < 1/8. Therefore,

E max I,J G I,J 2 op = 1 t log exp t E max I,J G I,J 2 op ≤ 1 t log E exp(t max I,J G I,J 2 op ) ≤ 1 t log I,J E exp(t G I,J 2 op ) ≤ 1 t log m 1 k m 2 q E exp(t H 2 op ) ≤ 1 t log e m 1 k k e m 2 q q e 8t(k+q) + 8t 1 -8t = 1 t k log m 1 k + q log m 2 q + k + q + 8t(k + q) + log 1 + 8t 1 -8t e -8t(k+q) ≤ 16 k log m 1 k + q log m 2 q + k + q + 8(k + q) + 8 1 -8t e -8t(k+q) ≤ 16 k log m 1 k + q log m 2 q + 2(k + q) ,
where in the last inequality we simply used 8/(1 -8t) = 8(k + q) and exp(-8t(k + q)) ≤ 1.

Proof [Propositon 15]

From Lemma 29 we have:

E Ω * k,q (G) = E max I∈G k ,J∈Gq G I,J op ≤ E max I∈G k ,J∈Gq G I,J 2 op 1 2 ≤ 4 k log m 1 k + q log m 2 q + 2(k + q) 1 2 ≤ 4 k log m 1 k + 2k + q log m 2 q + 2q
The upper bounds for the ℓ 1 and trace norms are standard. See Vershynin (2012, Theorem. 5.32) for the tight upper bound on the operator norm E G op ≤ √ m 1 + √ m 2 , and for the upper bound on the element-wise ℓ ∞ norm of G, use Jensen inequality followed by upper bounding the maximum of nonnegative scalars by their sum:

exp (t E G ∞ ) ≤ E exp (t G ∞ ) ≤ m 1 m 2 exp(t 2 /2) . Taking t = 2 log(m 1 m 2 ) in the logarithms of the last inequality gives E G ∞ ≤ √ 2m 1 m 2 .
C Some cone inclusions (Proofs of results in Section 4.2.2)

Let us start with a simple result useful to prove inclusions of tangent cones.

Lemma 30 Let f and g two convex functions from R d such that f ≤ g and let x * such that f (x * ) = g(x * ). Then T g (x * ) ⊂ T f (x * ).

Proof [Lemma 30]

Let h ∈ R d and τ > 0 such that g(x * + τ h) ≤ g(x * ). Then we also have

f (x * + τ h) ≤ g(x * + τ h) ≤ g(x * ) = f (x * ) ,
and therefore, for any τ > 0,

h ∈ R d : g(x * + τ h) ≤ g(x * ) ⊂ h ∈ R d : f (x * + τ h) ≤ f (x * ) .
From the definition (26) of the tangent cone we deduce, by taking the union over τ > 0 and the closure of this inclusion, that T g (x * ) ⊂ T f (x * ).

We can now prove the results in Section 4.2.2 Proof [Proposition 18] Consider a matrix A = ab ⊤ ∈ A k,q . We have A * = a 2 b 2 = 1, and A 1 = a 1 b 1 = √ kq. Since A is an atom of both the norm Ω k,q and the norm Ω k,q we have Ω k,q (A) = Ω k,q (A) = 1 so that, for any µ ∈ [0, 1],

Γ µ (A) = A * = 1 √ kq A 1 = Ω k,q (A) = Ω k,q (A) = 1 .
Besides, for any matrix

K ∈ R m 1 ×m 2 , for all (I, J) ∈ G m 1 k × G m 2 q , we have K I,J op ≤ K op and K I,J op ≤ K I,J Fro ≤ √ kq K I,J ∞ so that Ω * k,q (K) ≤ K op and Ω * k,q (K) ≤ √ kq max I,J K I,J ∞ =
√ kq K ∞ . Given that A k,q ⊂ A k,q , we also have that

Ω * k,q (K) = max A∈ A k,q A, K ≤ max A∈A k,q
A, K = Ω * k,q (K) .

By Fenchel duality, we therefore have for any Z ∈ R m 1 ×m 2 and µ ∈ [0, 1]:

µ √ kq Z 1 + (1 -µ) Z * ≤ Ω k,q (Z) ≤ Ω k,q (Z) .

Proof [Corollary 19]

Combining Proposition 18 with Lemma 30 directly gives (31). ( 32) is then a direct consequence of the definition of the statistical dimension ( 27).

Proof [Corollary 20]

A necessary and sufficient condition for exact recovery is the so called null space property which is the event that T Ω (Z * ) ∩ Ker(X ) = {0}, where Ker(X ) is the kernel of the linear transformation X (Chandrasekaran et al., 2012, Proposition 2.1). The result therefore follows from the inclusion of the cones stated in Corollary 19.

Proof [Proposition 21]

Let a ∈ A m k with supp(a) = I 0 , meaning that |a i | = 1/ √ k for i ∈ I 0 and a i = 0 for i ∈ I ∁ 0 . The sub differential of the scaled ℓ

1 norm Γ 1 at a is ∂Γ 1 (a) = s ∈ R m : s i = sign(a i ) for i ∈ I 0 , |s i | ≤ 1 for i ∈ I ∁ 0 .
From (10), we get that the subdifferential of θ k at a is

∂θ k (a) = {a + z : ∀i , a i z i = 0 and ∀I ∈ G m k , a I + z I ≤ 1} .
The first condition is equivalent to z i = 0 for i ∈ I 0 , which implies that the second is equivalent to

|z i | ≤ 1/ √ k for i ∈ I ∁ 0 .
We deduce that s = a + z ∈ ∂θ k (a) if and only if s i = a i for i ∈ I 0 and

|s i | ≤ 1/ √ k for i ∈ I ∁ 0 , i.e., ∂θ k (a) = 1 √ k ∂Γ 1 (a) .
This shows that the subdifferentials of Γ 1 and θ k have the same conic hull, and Proposition 21 follows by noting that the tangent cone is the polar cone of the conic hull of the subdifferential (Rockafellar, 1997, Theorem 23.7).

D Upper bound on the statistical dimension of Ω k,q (proof of Proposition 24)

The aim of this appendix is to prove the upper bound on the statistical dimension Ω k,q given in Proposition 24. Given its level of technicality, we split the proof in several parts. We start with preliminaries and notations in Section D.1, before proving Proposition 24 in Section D.2. The proofs of several technical results needed in Section D.2 are postponed to Section D.3, D.4 and D.5.

D.1 Preliminaries and notations

Let us start with some notations used throughout Appendix D. A = ab ⊤ ∈ A k,q is an atom of Ω k,q , with I 0 = supp(a) and J 0 = supp(b). γ = γ(a, b) refers to the atom strength of A (Definition 23).

For any I ∈ G m 1 k and J ∈ G m 2 q , let u I = a I / a I 2 and v J = b J / b J 2 . Note that while a I is a subvector of a, the notation u I does not refer to a subvector of some vector u and that therefore

[u I ] I 0 = [u I 0 ] I = a I since a I 0 = a = 1.
To analyze the statistical dimension (27) of Ω k,q at A, it is useful to express it as follows (Chandrasekaran et al., 2012, Proposition 3.6):

S(A, Ω k,q ) := E dist G, N Ω k,q (A) 2 , ( 50
)
where N Ω k,q (A) is the normal cone of Ω k,q at A (i.e., the conic hull of the subdifferential of Ω k,q at A) and dist G, N Ω k,q (A) denotes the Frobenius distance of the Gaussian matrix G with i.i.d. standard normal entries to N Ω k,q (A). In order to upper bound this quantity, it is therefore important to characterize precisely the normal cone N Ω k,q (A) .

For that purpose, let us introduce further notations. We consider the following subspace of R m 1 ×m 2

span(A) = LA + AR : L ∈ R m 1 ×m 1 , R ∈ R m 2 ×m 2 ,
and denote by P A and P ⊥ A the orthogonal projectors onto span(A) and span ⊥ (A) respectively. Since A = ab ⊤ with a 2 = b 2 = 1, we have the closed-form expressions

P ⊥ A (Z) = (Id m 1 -aa ⊤ )Z(Id m 2 - bb ⊤ ).
For any (I, J) ∈ G m 1 k × G m 2 q , consider now the subspace span I,J (A) = L I,I A I,J + A I,J R J,J :

L ∈ R m 1 ×m 1 , R ∈ R m 2 ×m 2 ,
and its orthogonal

span ⊥ I,J (A) = Z ∈ R m 1 ×m 2 : A I,J Z ⊤ I,J = A ⊤ I,J Z I,J = 0 .
Note that span ⊥ I 0 ,J 0 (A) is related to the subdifferential of Ω k,q at A, since according to (10) we can write it as

∂Ω k,q (A) = A + Z : Z ∈ span ⊥ I 0 ,J 0 (A) , ∀(I, J) ∈ G m 1 k × G m 2 q A I,J + Z I,J op ≤ 1 . ( 51
)
It is possible to estimate the dimension of span ⊥ I 0 ,J 0 (A) as follows:

Lemma 31 The dimension of span I 0 ,J 0 (A) is k + q -1.

Proof [Lemma 31]

For A = ab ⊤ , the range of L → L I 0 ,I 0 A I 0 ,J 0 equals the range of α I 0 → α I 0 b ⊤ which has dimension |I 0 | = k. By the same token, the range of R → A I 0 ,J 0 R J 0 ,J 0 has dimension q. By definition of span I 0 ,J 0 (A) we therefore have

span I 0 ,J 0 (A) = α I 0 b ⊤ + aβ ⊤ J 0 : α ∈ R m 1 , β ∈ R m 2
and therefore by the inclusion-exclusion principle dim span I 0 ,J 0 (A) = k + q -1.

Finally we denote by Π A,I,J the projector onto span I,J (A), and by Π ⊥ A,I,J the projector onto span ⊥ I,J (A). They satisfy respectively Π A,I,J (Z) = P A I,J (Z I,J ) and Π ⊥ A,I,J (Z) = Z -Π A,I,J (Z) = Z -P A I,J (Z I,J ) .

D.2 Proof of Proposition 24

Proof [Proposition 24] In order to upper bound the statistical dimension of Ω k,q at A, we associate to any matrix G a matrix Ξ(G) belonging to the normal cone N Ω k,q (A), where Ξ : R m 1 ×m 2 → R m 1 ×m 2 is measurable. From the characterization of the statistical dimension (50), since dist G, N Ω k,q (A) ≤ G -Ξ(G) Fro , we will then get the upper bound:

S(A, Ω k,q ) = E dist G, N Ω k,q (A) 2 ≤ E G -Ξ(G) 2 Fro . (52)
The main steps in the proof are then (i) to define the mapping Ξ, (ii) to show that Ξ(G) ∈ N Ω k,q (A) for all G, and (iiii) to upper bound E G -Ξ(G) 2 Fro in order to derive an upper bound on S(A, Ω k,q ) by ( 52). Given a measurable function ǫ : R m 1 ×m 2 → R, let us therefore consider the mapping Ξ:

∀G ∈ R m 1 ×m 2 , Ξ(G) := ǫ(G)A + Π ⊥ A,I 0 ,J 0 (G) . (53)
The following lemma provides a mapping ǫ to ensure that Ξ

(G) ∈ N Ω k,q (A). γ 2 G I 0 ,J 0 2 op ∨ max I∈G m 1 k J ∈G m 2 q G IJ 2 op ∨ max 0≤i<k 0≤j<q (i,j) =(0,0) 8 γ i k + j q max |I\I 0 |=i |J \J 0 |=j G ⊤ I∩I 0 ,J\J 0 u I 2 2 + G I\I 0 ,J∩J 0 v J 2 2 .
(54) Then, for every G ∈ R m 1 ×m 2 , the matrix Ξ(G) defined in (53) belongs to the normal cone of Ω k,q at A.

By choosing ǫ(G) as in Lemma 32, the upper bound (52) because Ξ(G) ∈ N Ω k,q (A). Using the decomposition G = Π A,I 0 ,J 0 (G) + Π ⊥ A,I 0 ,J 0 (G) we deduce

S(A, Ω k,q ) ≤ E G -Ξ(G) 2 Fro = E ǫ(G)A -Π A,I 0 ,J 0 (G) 2 Fro ≤ 2E ǫ(G)A 2 Fro + 2E Π A,I 0 ,J 0 (G) 2 Fro = 2E ǫ(G) 2 + 2(k + q -1), (55)
where ( 55) is due to A Fro = 1 and the fact that Π A,I 0 ,J 0 (G) 2 Fro follows a chi-square distribution with k + q -1 degrees of freedom, since by Lemma 31 this is the dimension of span I 0 ,J 0 (A). In order to upper bound E ǫ(G) 2 we need the following two lemmata in addition to Lemma 29.

Lemma 33

E G I 0 ,J 0 2 op ≤ 4(k + q) + 4 . (56)
Lemma 34

E max i,j 8
γ i k + j q max |J \J 0 |=j |I\I 0 |=i G ⊤ I∩I 0 ,J\J 0 u I 2 2 + G I\I 0 ,J∩J 0 v J 2 2 ≤ 48 γ (k ∨ q) log ((m 1 -k) ∨ (m 2 -q)) + 64 γ (k ∨ q) .
Combining Lemmata 29, 56 and 34 with the definition of ǫ(G) in (54) we deduce

E ǫ(G) 2 ≤ 16 γ 2 [4(k + q) + 4] + 16 k log m 1 k + q log m 2 q + 2(k + q) + 48 γ (k ∨ q) log ((m 1 -k) ∨ (m 2 -q)) + 64 γ (k ∨ q) ≤ 64 γ 2 + 64 γ + 32 (k + q + 1) + 16 k log m 1 k + q log m 2 q + 48 γ (k ∨ q) log (m 1 ∨ m 2 ) ≤ 160 γ 2 (k + q + 1) + 80 γ (k ∨ q) log (m 1 ∨ m 2 ) .
Plugging this upper bound into (55) finally proves Proposition 24.

D.3

The scaling factor ǫ(G) ensures that Ξ(G) ∈ N Ω k,q (A) (proof of Lemma 32)

Proof [Lemma 32] To simplify notations let us denote G := Π ⊥ A,I 0 ,J 0 (G) , so that (53) becomes Ξ(G) = ǫ(G)A + G. To prove that Ξ(G) belongs to the normal cone of Ω k,q at A, it is sufficient to prove that ǫ(G) -1 Ξ(G) = A + ǫ(G) -1 G is a subgradient of Ω k,q at A. By the characterization of the subgradient in (51), and since G ∈ span ⊥ I 0 ,J 0 (A), this is equivalent to

A IJ + ǫ(G) -1 GIJ op ≤ 1 for any (I, J) ∈ G m 1 k × G m 2 q , which itself is equivalent to A IJ + ǫ(G) -1 Π A,I,J ( G) op ≤ 1 and ǫ(G) -1 P ⊥ A ( GI,J ) op ≤ 1 . (57)
First, the second inequality of ( 57) is satisfied since

P ⊥ A ( GI,J ) op ≤ GI,J op = Π ⊥ A,I 0 ,J 0 (G) IJ op ≤ [G] IJ op ≤ ǫ(G) .
There thus remains to prove the first inequality of (57). Note that the matrix A IJ +ǫ(G) -1 Π A,I,J ( G) has rank 2, so its Frobenius norm is larger than its operator norm by at most a factor of √ 2. Working with the Frobenius norm is more convenient, so knowing that

A IJ + ǫ(G) -1 Π A,I,J ( G) 2 op ≤ A IJ + ǫ(G) -1 Π A,I,J ( G) 2 Fro ,
we will establish an upper bound on the latter quantity which we denote by ν I,J (G). Noting that

A IJ = a I 2 b J 2 u I v ⊤ J and that Π A,I,J ( G) = u I u ⊤ I GIJ + GIJ v J v ⊤ J -u I u ⊤ I GIJ v J v ⊤ J , we get ν I,J (G) = a I 2 b J 2 u I v ⊤ J + ǫ(G) -1 u I u ⊤ I GIJ + GIJ v J v ⊤ J -u I u ⊤ I GIJ v J v ⊤ J 2 Fro = a I 2 2 b J 2 2 + 2 ǫ(G) a I 2 b J 2 u ⊤ I GIJ v J + 1 ǫ(G) 2 u ⊤ I GIJ G⊤ IJ u I + v ⊤ J G⊤ IJ GIJ v J -2(u ⊤ I GIJ v J ) 2 ≤ a I 2 2 b J 2 2 + 2 ǫ(G) a I 2 b J 2 u ⊤ I GIJ v J + 1 ǫ(G) 2 u ⊤ I GIJ G⊤ IJ u I + v ⊤ J G⊤ IJ GIJ v J .
The following Lemma provides upper bounds on the different terms.

Lemma 35 We have

u ⊤ I GIJ v J ≤ a I 0 \I 2 b J 0 \J 2 G I 0 J 0 op , u ⊤ I GIJ G⊤ IJ u I ≤ G ⊤ I∩I 0 ,J\J 0 u I 2 2 + 2 a I 0 \I 2 2 G I 0 ,J 0 2 op , v ⊤ J G⊤ IJ GIJ v J ≤ G I\I 0 ,J∩J 0 v J 2 2 + 2 b J 0 \J 2 2 G I 0 ,J 0 2 op .
This yields

ν I,J (G) ≤ a I 2 2 b J 2 2 + 2 ǫ(G) a I 2 b J 2 a I 0 \I 2 b J 0 \J 2 G I 0 J 0 op + 1 ǫ(G) 2 G ⊤ I∩I 0 ,J\J 0 u I 2 2 + 2 a I 0 \I 2 2 G I 0 ,J 0 2 op + 1 ǫ(G) 2 G I\I 0 ,J∩J 0 v J 2 2 + 2 b J 0 \J 2 2 G I 0 ,J 0 2 op ≤ a I 2 2 b J 2 2 + γ 2 a I 2 b J 2 a I 0 \I 2 b J 0 \J 2 + γ 8 i k + j q + γ 2 8 a I 0 \I 2 2 + b J 0 \J 2 2 ,
where we used the definition of ǫ(G) (54) to derive the last inequality.

Define

α := a I 0 \I 2 = 1 -a I 2 and β := b J 0 \J 2 = 1 -b J 2 .
With these notations and rearranging the terms, we can rewrite the above inequality as

ν I,J (G) ≤ (1 -α)(1 -β) + γ 2 αβ(1 -α)(1 -β) + γ 2 8 (α + β) + γ 8 i k + j q .
Since 0 ≤ α, β ≤ 1 and using

√ αβ ≤ 1 2 (α + β), we have αβ ≤ 1 2 (α + β) and αβ(1 -α)(1 -β) ≤ 1 2 (α + β) .
These inequalities yield

ν I,J (G) ≤ 1 + (α + β) -1 + 1 2 + γ 4 + γ 2 8 + γ 8 i k + j q .
By definition of γ = min ι∈I 0 ι ′ ∈J 0 k a 2 ι , q b 2 ι ′ , we have i k ≤ α γ and j q ≤ β γ . Moreover, given that 0 ≤ γ ≤ 1, we have 4 γ -2γ = 1 γ (4 -2γγ 2 ) ≥ 1 γ , so that factorizing γ 8 in the previous expression, we obtain

ν I,J (G) ≤ 1 + γ 8 - 4 γ + 2 + γ (α + β) + i k + j q ≤ 1 + γ 8 - 1 γ (α + β) + i k + j q ≤ 1 ,
which concludes the proof.

D.4 Proof of Lemma 35

Let us first start with a few useful technical lemmas.

Lemma 36 The matrix GIJ = [Π ⊥

A,I 0 ,J 0 (G)] IJ is of the form GIJ = G1 + G2 with

G1 = G IJ -G I∩I 0 ,J∩J 0 and G2 = (Id I -a I a ⊤ ) G I 0 J 0 (Id J -bb ⊤ J ). Proof [Lemma 36] Π ⊥ A,I 0 ,J 0 (G) = G -Π A,I 0 ,J 0 (G) = G -a I 0 a ⊤ I 0 G I 0 J 0 -G I 0 J 0 b J 0 b ⊤ J 0 + a I 0 a ⊤ I 0 G I 0 J 0 b J 0 b ⊤ J 0 = G -G I 0 J 0 + (Id I 0 -a I 0 a ⊤ I 0 ) G I 0 J 0 (Id J 0 -b J 0 b ⊤ J 0 ), so that [Π ⊥ A,I 0 ,J 0 (G)] IJ = G IJ -G I∩I 0 ,J∩J 0 + (Id I -a I a ⊤ ) G I 0 J 0 (Id J -bb ⊤ J ).
Lemma 37 We have u

⊤ I G1 = u ⊤ I G I∩I 0 ,J\J 0 and G1 v J = G I\I 0 ,J∩J 0 v J .
Proof [Lemma 37] Given that supp(u I ) ⊂ I 0 , we have

u ⊤ I G1 = u ⊤ I (G IJ -G I∩I 0 ,J∩J 0 ) = u ⊤ I (G I∩I 0 ,J -G I∩I 0 ,J∩J 0 ) = u ⊤ I G I∩I 0 ,J\J 0 ,
which proves the first equality. The second one is proved similarly.

Lemma 38 Id -b J b ⊤ 2 op ≤ 4 3 Proof [Lemma 38]
The largest singular value is attained on the span of b J and b J c both on the left and on the right.

Given that b = 1, it is therefore also the largest eigenvalue of the matrix of the linear operator restricted to this span which is equal to

(1 -x) -(1 -x)x 0 1 , for x = b J 2 .
Tedious but simple calculations show that the squared operator norm of this matrix is equal to 1x/2 + 1/2 x(4 -3x), which takes its maximum value 4/3 for x = 1/3.

Proof [Lemma 35]

Given that GIJ = G1 + G2 and u ⊤ I G1 = u I GI∩I 0 ,J\J 0 , we have u

⊤ I G1 v J = u ⊤ I G1 v J∩J 0 = 0, so that u ⊤ I GIJ v J = u ⊤ I G2 v J = u ⊤ I (Id I -a I a ⊤ ) G I 0 J 0 (Id J -bb ⊤ J )v J ≤ u I -a I a G I 0 J 0 op v J -b J b ≤ a I 0 \I b J 0 \J G I 0 J 0 op , because u ⊤ I (Id I -a I a ⊤ ) 2 = u I -a I a 2 = 1 -2 a I 2 + a I 2 = a I 0 \I 2 , and symmetrically v J -b J b = b J 0 \J
. This shows the first inequality. For the two next inequalities, note that

u ⊤ I GIJ G⊤ IJ u I = G⊤ IJ u I 2 = G⊤ 1 u I 2 + G⊤ 2 u I 2
because G⊤ 1 u I , G⊤ 2 u I = 0 as a result of the fact that by lemma 37, G⊤ 1 u I and G⊤

2 u I have disjoint supports. Now G⊤ 1 u I 2 = G ⊤ I∩I 0 ,J\J 0 u I 2 2 and G⊤ 2 u I ≤ 2 a I 0 \I 2 G I 0 ,J 0 2 op , because Id -b J b ⊤ 2 op ≤ 2 (see
√ k + √ q + s 2 ≤ 2 ( √ k + √ q) 2 + s 2 gives P G I 0 ,J 0 2 op > 2 ( √ k + √ q) 2 + s 2 ≤ exp(-s 2 /2) . Setting t = 2s 2 yields P G I 0 ,J 0 2 op > 4(k + q) + t ≤ exp(-t/4) . It follows that E G I 0 ,J 0 2 op = ∞ 0 P( G I 0 ,J 0 2 op ≥ t ′ )dt ′ = 4(k+q) 0 dt ′ + ∞ 4(k+q) P( G I 0 ,J 0 2 op ≥ t ′ )dt ′ ≤ 4(k + q) + ∞ 0 exp(-t/4)dt = 4(k + q) + 4 .

Proof [Lemma 34]

As the sets I ∩ I 0 × J\J 0 and I\I 0 × J ∩ J 0 are disjoint, and u I , v J of unit length, the random variable

M I,J = G ⊤ I∩I 0 ,J\J 0 u I 2 2 + G I\I 0 ,J∩J 0 v J 2 2
follows a chi-square distribution with i + j degrees of freedom, where i = |I\I 0 | and j = |J\J 0 |. Using Chernoff's inequality and the form of the chi-square moment generating function, we have that for any fixed real number α and fixed index sets I and J, for all t ∈ (0, 1/2), P M I,J > α = P e tM I,J > e tα ≤ e -tα E e tM I,J = e -tα (1 -2t) -i+j 2 .

Taking the maximum over index sets I and J with the same intersection sizes with I 0 and J 0 respectively, and using a union bound on the independent choices of I and J, yields

P   max |I\I 0 |=i |J \J 0 |=j M I,J > α   ≤ m 1 -k i m 2 -q j exp -tα - i + j 2 log(1 -2t)
≤ exp -tα -i + j 2 log(1 -2t) + i log(m 1k) + j log(m 2q) . ≤ exp (i + j) -tλ -1 2 log(1 -2t) + log(m 1k) .

Let us introduce M i,j = 1 i+j max |I\I 0 |=i |J \J 0 |=j M I,J , and take t = 1 2 1 -1 m 1 -k < 1 2 . Then

P    max 0≤i<k 0≤j<q (i,j) =(0,0) M i,j > λ    ≤ 0≤i<k 0≤j<q (i,j) =(0,0) exp (i + j) - 1 2 1 - 1 m 1 -k λ + 3 2 log(m 1 -k) = k-1 i=0 β i q-1 j=0 β j -1 = 1 -β k 1 -β 1 -β q 1 -β -1 ≤ 2β ,
where

β = exp - 1 2 1 - 1 m 1 -k λ + 3 2 log(m 1 -k) .
As a consequence, we have

E[max i,j M i,j ] = ∞ 0 P[max i,j M i,j > λ]dλ ≤ 3(m 1 -k) m 1 -k-1 log k 0 dλ + 2 ∞ 3(m 1 -k) m 1 -k-1 log(m 1 -k) exp 3 2 log(m 1 -k) - 1 2 1 - 1 m 1 -k λ dλ ≤ 3(m 1 -k) m 1 -k -1 log k + 4 m 1 -k m 1 -k -1 ≤ 6 log(m 1 -k) + 8 . It follows that E max 0≤i<k 0≤j<q (i,j) =(0,0) 8 γ i k + j q max |J \J 0 |=j |I\I 0 |=i G ⊤ I∩I 0 ,J\J 0 u I 2 2 + G I\I 0 ,J∩J 0 v J 2 2 ≤ 48 γ (k ∨ q) log ((m 1 -k) ∨ (m 2 -q)) + 64 γ (k ∨ q) . (58)
E Lower bound on the statistical dimension of Γ µ (Proof of Proposition 25)

Let us start with a technical lemma:

Lemma 39 Let ab ⊤ ∈ A k,q , X : R m 1 ×m 2 → R n a linear map from the standard Gaussian ensemble and y = X (ab ⊤ ). then, with probability 1c 1 exp(-c 2 n 0 ), solving formulation (28) with the norm Γ µ fails to recover ab ⊤ simultaneously for any values of µ ∈ [0, 1], where c 1 and c 2 are universal constants.

Proof [Lemma 39] The proof consists in applying theorem 3.2 in [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF] for the combination of the ℓ 1norm with the trace norm. We adapt slightly the notations of that paper to reflect the fact that we are working with matrices. Since we consider conic combinations of the ℓ 1 and trace norms, the number of norms is therefore τ = 2. To apply the theorem we need to specify κ, θ, d min , γ and C • in the notations of that paper.

For each decomposable norm ν j for j ∈ {1, 2}, with ν 1 the ℓ 1 -norm and and ν 2 the trace norm, given a point ab ⊤ (which corresponds to the point x 0 in [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF], the authors define

• T j the supporting subspaces and E j (e j in the paper), the orthogonal projection of any subgradient of the norm in ab ⊤ (Definition 2.1),

• L j the Lipschitz constant of ν j with respect to the Euclidean norm (Definition 2.2),

• κ j = E j 2 Fro L 2 j m 1 m 2 dim(T j ) (Definition 2.2).
Let ab ⊤ ∈ A k,q with support I 0 × J 0 and s a = sign(a), s b = sign(b). Denoting e ij the element of the canonical basis of R m 1 ×m 2 , we have

• T 1 = span({e ij } (i,j)∈I 0 ×J 0 ) so that dim(T 1 ) = kq,

• T 2 = {av ⊤ + ub ⊤ | u ∈ R m 1 , v ∈ R m 2 } so that dim(T 2 ) = m 1 + m 2 -1.
By definition d min = dim(T 1 ) ∧ dim(T 2 ). We have

E 1 = s a s ⊤ b , E 1 2 Fro = kq, E 2 = ab ⊤ , E 2 2 Fro = 1, L 1 = kq, L 2 = √ m 1 ∧ m 2 ,
and thus

κ 1 = m 1 m 2 kq , κ 2 = m 1 m 2 (m 1 ∧ m 2 )(m 1 + m 2 -1)
, so that κ = κ 1 ∧ κ 2 ≥ 1 2 .

We then have θ defined as θ = θ 1 ∧ θ 2 with θ j = E ∩,j 2 / E j 2 where E ∩,j is the projection of E j on T 1 ∩ T 2 . But E 2 ∈ T 1 so that θ 2 = 1. The situation is less simple for E 1 . Indeed, E ∩,1 = a 1 as ⊤ b + b 1 s a b ⊤ab ⊤ a 1 b 1 . Some calculations lead to

θ 2 1 = a 2 1 k + b 2 1 q - a 2 1 k b 2 1 q ,
hence the definition of ζ(a, b) = θ 2 = θ 2 1 ∧ θ 2 2 . Theorem 3.2 in [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF] offers the possibility of constraining the estimator to lie in a cone C. In our case, C = R m 1 ×m 2 , given the definition of γ we therefore have γ ≤ 2. The result follows from applying the theorem with θ 2 = ζ(a, b) and using κ 81γ 2 τ ≥ 1/2 3 4 .2 2 .2 = 1 6 4 .

Lemma 41 Let G ∈ R n be an standard normal vector, then we have

E[κ * k (G)] ≥ 2 π k log n + 1 k + 1 .
Proof [Lemma 41] Denote by F the cdf of the absolute value of a standard normal variable. Then,

F (x) = Φ(x) -Φ(-x) = erf x √ 2 ,
where Φ is the cdf of a standard Gaussian and erf denotes the error function. We use the following inequality due to [START_REF] Chu | On bounds for the normal integral[END_REF]:

1e -x 2 ≤ erf(x) ≤ 1e -π 4 x 2 , to deduce that

F -1 (y) ≥ - 2 π log(1 -y 2 ) .
By definition, we have

E[κ * k (G)] = 1 √ k E[X (n) + . . . + X (n-k+1)
] where X i = |G i | and G is a vector of independent standard normal variables. It can easily be checked that F -1 is a convex function. This implies, using Lemma 40, that

E[κ * k (G)] ≥ 1 √ k k j=1 F -1 1 - j n + 1 ≥ √ k F -1 1 k k j=1 1 - j n + 1
(again by Jensen's inequality)

= √ k F -1 1 - k + 1 2(n + 1) ≥ √ k - 2 π log k + 1 (n + 1) - k + 1 2(n + 1) 2 ≥ 2 π k log n + 1 k + 1 .

Proof [Proposition 26]

We will denote the squared Gaussian width of the tangent cone intersected with a Euclidean unit ball by w(T κ k (a) ∩ S m-1 ) = E max

t∈Tκ k (a)∩S m-1 t, G ,
where G ∈ R m denotes a standard Gaussian vector. We have w(T κ k (a)∩S m-1 ) 2 ≤ S(a, κ k ) (Chandrasekaran et al., 2012, Proposition 3.6). We thus seek a lower bound of w(T κ k (a) ∩ S m-1 ). Since the tangent cone is polar to the normal cone, we have that F.2 Upper bound on the statistical dimension of θ k (Proof of Proposition 27)

Proof [Proposition 27] Without loss of generality, let us assume that w ∈ R p is a fixed vector having nonincreasingin absolute value -coordinates, the first s of which are assumed to be nonzero. We compute the subdifferential of θ k (w) directly by using ( 14). Remember that one characterization of the subdifferential is for i ∈ I 1 .

As for i ∈ I 0 , the coefficients α i do not impact α ⊤ w so they should also not impact θ * k (α). If s < k this implies α i = 0, and if s ≥ k this means |α i | ≤ |α k |, and in that case k ∈ I 1 . With the convention w I 1 1 = 0 when I 1 = ∅, we finally get the following expression for the subdifferential:

∂θ k (w) = 1 θ k (w) w I 2 + 1 r + 1 w I 1 1 (sgn(w I 1 ) + h I 0 ) : h ∞ ≤ 1 . ( 60
)
In the case s < k, we have s = kr + 1, I 2 = [1, s], I 1 = ∅ and I 0 = [s + 1, p]. In that case θ k (w) = w 2 and ∂θ k (w) = w/ w 2 , showing that θ k is differentiable at w, meaning θ k is useless to recover w.

Let us therefore only consider the case s ≥ k, in which case I 1 = ∅ and w I 1 1 > 0. In order to compute the statistical dimension of θ k at w, we use the characterization (50)

S(w, θ k ) = E dist (g, N θ k (A)) 2 ,
where g is a p-dimensional random vector with i.i.d. normal entries and N θ k (A) is the conic hull of ∂θ k (w). We then get:

S(w, θ k ) = E inf t>0 & u∈t∂θ k (w) u -g 2 2 ≤ inf t>0 E inf u∈t∂θ k (w) u -g 2 2 ≤ inf t>0 E inf h∈R p , h ∞≤1 g I 2 -t (r + 1) w I 1 1 w I 2

  | wi | ≥ | wk-r |, and where by convention | w0 | = ∞.

Figure 2 :

 2 Figure 2: Estimates of the statistical dimensions of the ℓ 1 , trace and Ω k,q norms at a matrix Z ∈ R 1000×1000 in different setting. Top left: Z is an atom in A k,k for different values of k. Top right: Z is a sum of r atoms in A k,k with non-overlapping support, with k = 10 and varying r. Bottom left: Z is a sum of 3 atoms in A k,k with non-overlapping support, for varying k. Bottom right: Z is a sum of 3 atoms in A k,k with overlapping support, for varying k.

Figure 3 :

 3 Figure 3: Sparse PCA example. The first row shows the supports found by our method (left) by sequential sparse PCA (middle) and element wise thresholding of the sample covariance matrix. Other plots contain heatmaps of the estimated covariance matrix using different methods, and the ground truth Σ ⋆ in the lower right hand side.

  Lemma 38 for a proof). This shows the second inequality and the third follows by symmetry. D.5 Upper bounds for ǫ(G) 2 (Proofs of Lemmata 33 and 34) Proof [Lemma 33] Using (45) and the fact that

  Taking α = λ(i + j), we have for any t < 1/2 (assuming w.l.o.g.m 1k ≥ m 2q) -tλ(i + j) -i + j 2 log(1 -2t) + i log(m 1k) + j log(m 2q)

  If n ≤ 1 9 m 1 m 2 and further n ≤ n 0 := ζ(a, b) 1 6 4 (kq) ∧ (m 1 + m 2 -1) -2, with ζ(a, b) = 1 -1 -

T

  κ k (a) = {t ∈ R m | s, t ≤ 0, ∀s ∈ ∂κ k (a)} .Given a random Gaussian vector G, denote I 0 the support of a and I G the indices of the k largest coefficients of G in absolute value outside of I 0 . Denote by sG = sign(G I G ), i.e., the vector whose entries are zero outside of I G and equal to the sign of the corresponding coefficient of G otherwise.Define t G = 1 √ 2k (s Ga). By construction t G ∈ S m-1 . Let now consider s ∈ ∂κ k (a), we have √ 2k s, t G =s, a + s, sG ≤ -1 + κ k (s G ) κ * k (s) ≤ -1 + 1 = 0, so that t G ∈ T κ k (a). Therefore w(T κ k (a) ∩ S m-1 ) ≥ E[ t G , G ] = 1 2 √ k E[ sG , G ] = 1 2 E[κ * k (G)], whence the result using Lemma 41 and w(T κ k (a) ∩ S m-1 ) 2 ≤ S(a, κ k ).

  ∂θ k (w) = {α ∈ R p : θ * k (α) ≤ 1 , α ⊤ w = θ k (w)} . Letting r ∈ {0, • • • , k -1} being the unique integer such that |w k-r-1 | > 1 r+1 p i=k-r |w i | ≥ |w k-r |, let us partition the set of entries {1, • • • , p} into I 2 = {1, • • • , kr -1}, I 1 = {kr, • • • , s} and I 0 = {s + 1, • • • , p} (where each set may be empty). Then we can rewrite the expression of the k-support norm (14) asθ k (w) 2 = w I 2 Then necessarily each element α ∈ ∂θ k (w) must satisfy    α i = w i θ k (w)for i ∈ I 2 , α i = w I 1 1 sign(w i ) (r+1)θ k (w)

seeRockafellar (1997), p.

28, for a precise definition of gauge functions.

This is possible because Ω k, is only a gauge and not a norm.

Similar bounds could be derived with large probability for the non-oracle estimator by controlling the deviations of Ω * (G) from its expectation.

As detailed later, the tangent cone is the closure of the cone of descent directions.

Note that the scaling ensures that Γµ(A) = 1 for µ ∈ [0, 1] and A ∈ A k,q .

This result is actually stated informally for the special case of k = q = √ m = with m = m1 = m2 in the context of a discussion of the planted clique problem in[START_REF] Chandrasekaran | Computational and statistical tradeoffs via convex relaxation[END_REF].

Note that this implies that the essential support of the random variable is bounded below.

Acknowledgments

We would like to thank Francis Bach for interesting discussions related to this work. This work was supported by the European Research Council (SMAC-ERC-280032) and by by Agence Nationale de la Recherche (ANR-13-MONU-005-10)

Proof [Proposition 25] Take M such that when m 1 , m 2 , k, q, m1/k, m 2 /q ≥ M then n 0 is large enough to ensure 1c 1 exp(-c 2 n 0 ) > 4 exp (-32/17). Then, according to Lemma 39, solving (28) with the norm Γ µ fails to recover A = ab ⊤ with probability at least 4 exp (-32/17). On the other hand, Amelunxen et al. (2013, Theorem 7.1) shows that, when n ≥ S (A, Γ µ ) + λ, for any λ ≥ 0, then solving (28) with the norm Γ µ correctly recovers A with probability at least

where

. Take λ = 16ω(A, Γ µ ), then using the fact that ω(A, Γ µ ) ≥ 1 we get that the probability ( 59) is smaller than 4 exp (-32/17). This implies that

F Bounds on the statistical dimension in the vector case (proofs of results of Section 4.2.4)

F.1 Lower bound on the statistical dimension of κ k (Proof of Proposition 26)

Let us start with two technical lemmata.

Lemma 40 Let X (k) denote the kth order statistics of an i.i.d. sample X 1 , . . . , X n whose common distribution has a cdf F . Assume that

.