Bruno Arfib

Luc Vanrell

Michel Olive

New insights into the Cosquer art cave hydrogeological functionning (France)

teaching and research institutions in France or abroad, or from public or private research centers.

New insights into the Cosquer art cave hydrogeological functionning (France)

Arfib Bruno 1 , Luc Vanrell 2 , Michel Olive 3 1-Aix Marseille Univ, CNRS, IRD, INRA, Coll France, CEREGE, Aix-en-Provence, France Email : arfib@cerege.fr 2-Immadras & LAMPEA Aix Marseille Univ, France 3-DRAC, Service Régional de l'Archéologie, & LAMPEA Aix Marseille Univ, France Key words : Art cave, conservation, overpressure, monitoring

The Cosquer cave supports and protects some paleolithic paintings and engravings, dated to more than 31,000 years (Cal BP, [START_REF] Valladas | Radiocarbon dating of the decorated Cosquer cave (France)[END_REF]). It's a coastal cave, located in the Calanques massif, near Marseille in south of France. This area is well-known for its karstic landscape, in the white urgonian limestones (Barremian, early cretaceous). Nowadays, the cave has no water-free entrance. The only way to access to the cave is to dive to a submarine entrance giving access to a karst conduit connected with the non-flooded part of the cave (Figure 1). During paleolithic times, the seawater level was lower (down to 135 m). The access to the cave to the paleolithic men was flooded by the Mediterranean Sea rise around 10,000 years (Cal BP, [START_REF] Lambeck | Sea-level change along the French Mediterranean coast for the past 30 000 years[END_REF]. This specific location of the cave offered a protected area for the conservation of the rock art: no man entrance during the historical time, climatic and environmental steady conditions. Moreover, the karst also protected the rock art because it limited the sea-level rise within the cave. Indeed, the water level inside the Cosquer cave is lower than the sea-level, although only a tens of meters of limestones separate the cave to the sea. Obviously, the cave is a confined environment and is an interesting case-study to understand the impact of permeability contrasts between open karst features and the surrounding matrix. The aims of this work are: (1) to present a first long pressure time series ever recorded in the Cosquer cave, (2) to show which phenomena control the water level variation inside the cave, in order to answer to the following questions: when, how high and why the water level varies in the cave? This unexpected low water level in the cave was shown since the first pressure measurements following the discovery [START_REF] Vouvé | Caractérisation physique et environnementale d'un sanctuaire préhistorique sous-marin semi-noyé et orné préalablement à l'élaboration d'une démarche conservatoire[END_REF]. The air pressure in the cave is higher than the atmospheric pressure outside the cave. This air overpressure pushes down the water level and P air_cave WL cave WL sea P atmo avoids the water to rise on paintings and engravings located close to the sea-level, e.g. the horses panel. The air overpressure changes over the year and influences the art conservation. However, few measurements have been done to study this phenomenon. In 2014, on request of the regional agency of cultural affairs in charge of the study and conservation of the Cosquer cave (DRAC PACA, France), the CEREGE laboratory started a new scientific survey of the hydrogeological functionning of the cave. Pressure sensors have been installed in-situ, with a 5 minutes time-step recording, inside the cave in the air and in the water, in the sea, and in the air outside the cave (Figure 1). Pressure is converted to fresh or salted water column. We also beneficiated from the measurements done at the Port-Miou observatory (SNO Karst) located 5 km eastward from the cave, that gives access to pressure data and that can be used as reference for the hydrological states of the karst aquifers in the area [START_REF] Arfib | Insights into saline intrusion and freshwater resources in coastal karstic aquifer using a lumped Rainfall-Discharge-Salinity model (the Port-Miou brackish spring, SE France)[END_REF].

Figure 2: The water level inside the Cosquer cave at three hydrologic periods: a) 04/10/2014, the water level is low, the air pressure inside the cave is high; b) 24/08/2017, the water level is high, the bottom of the horses panel is flooded; c) 27/09/2017, the water level is very high, the air pressure in the cave decreased close to the outside atmospheric pressure.

The three years of data show that the cave air pressure is always higher than the normal atmospheric pressure. The air overpressure ranges between a few centimeters to 1.2 m. Water level in the cave is the same in the several pools. It varies at the annual scale up to 1.2m, correlated with the air overpressure variations. Taking the horses panel as a reference art rock in the cave, the paintings are usually out of water (Figure 2a), but can be partially flooded from 1 to 3 months depending on the year, during summer and early autumn (Figure 2b,c). Water level (or air pressure) varies at several scales. Daily, the sea tide is transferred within the coastal cave, but the water level variation is limited by the cave air volume. This clearly confirms that the cave behaves as a confined medium. At the annual scale, short events have a very high impact, decreasing the water level in the cave to more than 1 meter in a few hours. In this case, the water level decrease is mainly due to an equivalent increase of air overpressure. We showed that these events are generated by waves outside the cave. Waves can transfer air through the limestone massif by karst or cracks usually flooded. When flooded the submarine karst paths are limited to water transfer and the cave remains confined. The karst massif can be conceptualized by a vadose zone with very low permeability, and a saturated zone below the mean sea-level where karst network is open (Figure 3). Karst network geometry should be special and connected with the waves properties in order to allow the air to flow only in one way from the sea to the cave. As a first step of the further work still needed, we showed that the overpressure events are linked with direction and height of the waves. This study shows that karst environment plays an essential role in the conservation of our archeological natural heritage. Permeability in a karst massif can be highly heterogeneous at various scales; we show that even at the scale of a karst cave the permeability could be contrasted, e.g. very low in the vadose zone and high in the saturated zone in the Cosquer cave.

Figure 1 :

 1 Figure 1 : Schematic cross-section of the Cosquer cave, in the Calanques National Park, Marseille, France. Automatic pressure sensors have been installed: (1) in the sea in front of the submarine entrance (WLsea), (2) inside the cave in two pools (WLcave) and in the air (Pair_cave), (3) in the air outside the cave (Patmo) at the Port-Miou observatory (SNO Karst) located 5 km eastward from the cave.

Figure 3 :

 3 Figure 3: Conceptual cross-section of the Cosquer karst functionning. The cave is partly confined. Tide variations propagate inside the cave but are lower than the sea-tide (black curve). Specific waves height and direction (red curve) inject air inside the cave and generate an air overpressure that decreases the water level inside the cave.

Acknowledgements :

This work has been possible thanks to the partnership between the DRAC -SRA (Service Régional de l'Archéologie, France) and the laboratory CEREGE. The authors would like to thank: (1) Mr. Xavier Delestre (SRA) for his support in this study, (2) Mr. Claude Vella and Mr. Pierre Rochette (CEREGE) for their help on the field, (3) the Immadras team, Mr. Eric Lesomptier the ship captain, and the divers Anne Delhomme and Fabrice Dudenhofer. This work beneficiated of data recorded in the Port-Miou observation site, part of the KARST observatory network (www.sokarst.org) initiative from the INSU/CNRS, which aims to strengthen knowledge-sharing and promote cross-disciplinary research on karst systems.


Ivan Dokmani Ć

R Émi Gribonval

I Dokmanic

CONCENTRATION OF THE FROBENIUS NORM OF GENERALIZED MATRIX INVERSES

In many applications it is useful to replace the Moore-Penrose pseudoinverse (MPP) by a different generalized inverse with more favorable properties. We may want, for example, to have many zero entries, but without giving up too much of the stability of the MPP. One way to quantify stability is by how much the Frobenius norm of a generalized inverse exceeds that of the MPP. In this paper we derive finite-size concentration bounds for the Frobenius norm of p -minimal general inverses of iid Gaussian matrices, with 1 ≤ p ≤ 2. For p = 1 we prove exponential concentration of the Frobenius norm of the sparse pseudoinverse; for p = 2, we get a similar concentration bound for the MPP. Our proof is based on the convex Gaussian min-max theorem, but unlike previous applications which give asymptotic results, we derive finite-size bounds.

1. Introduction. Generalized inverses are matrices that have some properties of the usual inverse of a regular square matrix. We call1 X ∈ R n×m a generalized inverse of a matrix A ∈ R m×n if AXA = A, and write G(A) for the set of all such matrices X. In inverse problems it is desirable to use generalized inverses with a small Frobenius norm because the Frobenius norm controls the output mean-squared error. In this paper, we study Frobenius norms of generalized inverses that are obtained by constrained minimization of a class of matrix norms. Concretely, we look at entrywise p norms for 1 ≤ p ≤ 2, including the Moore-Penrose pseudoinverse (MPP) for p = 2 and the sparse pseudoinverse for p = 1.

For A ∈ R m×n , m < n, 1 ≤ p ≤ ∞, we define the p -minimal generalized inverse as

2 ginv p (A) def = arg min X X p subject to X ∈ G(A), with M p = ij |m ij | p 1/p .
The MPP A † is obtained by minimizing the Frobenius norm for p = 2, thus ginv p (A) F ≥ A † F for any p. Computing ginv p (A) involves solving a convex program.

Our initial motivation for this work is the sparse pseudoinverse, p = 1, since applying a sparse pseudoinverse requires less operations than applying a full one [START_REF] Dokmanić | Beyond Moore-Penrose: Sparse pseudoinverse[END_REF][START_REF] Li | Sparse Dual Frames and Dual Gabor Functions of Minimal Time and Frequency Supports[END_REF][START_REF] Casazza | Optimally Sparse Frames[END_REF][START_REF] Krahmer | Sparsity and Spectral Properties of Dual Frames[END_REF]. The sparsest generalized inverse may be formulated as (1.1) ginv 0 (A) def = arg min X X 0 subject to X ∈ G(A), where • 0 counts the total number of non-zero entries. The non-zero count gives the naive complexity of applying X or its adjoint to a vector. We show in Section 2 that for a generic A, (1.1) has many solutions. While some of them are easy to compute, they correspond to poorly conditioned matrices.

To recover uniqueness and improve conditioning of sparse pseudoinverses, it is natural to try and replace 0 by the 1 norm [START_REF] Donoho | Compressed Sensing[END_REF]. Indeed, it was shown in [START_REF] Dokmanic | Beyond moore-penrose part II: the sparse pseudoinverse[END_REF] that ginv 1 (A) provides a minimizer of the 0 norm for almost all matrices, and that this minimizer is generically unique, motivating the notation spinv(A) def = ginv 1 (A). Intuitively, an m × n matrix A with m ≤ n is generically rank m, hence AX = I m is a system of m 2 independent linear equations. The matrix X has nm entries, leaving us with nmm 2 degrees of freedom, which one hopes will correspond to nmm 2 zero entries. The main advantage of spinv over 0 minimization is that it yields unique, well-behaved matrices.

1.1. Our Contributions. In Sections 2 and 3 we prove an exponential concentration result for the Frobenius norm of p -minimal pseudoinverses for iid Gaussian matrices. Specializing to p = 1 in Corollary 2.4, we show that unlike simpler strategies that yield a sparsest generalized inverse, 1 minimization produces a well-conditioned matrix; specializing to p = 2 in Corollary 2.3, we get new results for the Frobenius norm of the MPP. Unlike previous applications of the CGMT, we give finite-size concentration bounds rather than asymptotic "in probability" results.

Prior Art.

There is a one-to-one correspondence between generalized inverses of full rank matrices and dual frames. Several earlier works [START_REF] Casazza | Optimally Sparse Frames[END_REF][START_REF] Krahmer | Sparsity and Spectral Properties of Dual Frames[END_REF][START_REF] Li | Sparse Dual Frames and Dual Gabor Functions of Minimal Time and Frequency Supports[END_REF] study existence and explicit constructions of sparse frames and sparse dual frames. Krahmer, Kutyniok, and Lemvig [START_REF] Krahmer | Sparsity and Spectral Properties of Dual Frames[END_REF] establish sharp bounds on the sparsity of dual frames, showing that generically, for A ∈ C m×n , the sparsest dual has mnm 2 zeros, while Li, Liu, and Mi [START_REF] Li | Sparse Dual Frames and Dual Gabor Functions of Minimal Time and Frequency Supports[END_REF] provide better bounds on the sparsity of dual Gabor frames. They introduce the idea of using 1 minimization to find these dual frames, and show that under certain conditions, 1 minimization yields the sparsest possible dual Gabor frame. Further examples of non-canonical dual frames are given by Perraudin et al., who use convex optimization to derive dual frames with good time-frequency localization [START_REF] Perraudin | Designing Gabor Windows Using Convex Optimization[END_REF].

Results on finite-size concentration bounds for norms of pseudoinverses are scarce, with one notable exception being an upper bound on the probability of large deviation for the MPP [START_REF] Halko | Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[END_REF] (we obtain concentration bounds for a complementary regime). On the other hand, a number of results exist for square matrices [START_REF] Rudelson | Invertibility of random matrices: norm of the inverse[END_REF][START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF]. The sparse pseudoinverse was previously studied in [START_REF] Dokmanić | Beyond Moore-Penrose: Sparse pseudoinverse[END_REF], where it was shown empirically that the minimizer is indeed a sparse matrix, and that it can be used to speed up the resolution of certain inverse problems.

Our proof relies on the convex Gaussian min-max theorem (CGMT) [START_REF] Oymak | The Squared-Error of Generalized LASSO: A Precise Analysis[END_REF][START_REF] Thrampoulidis | Precise Error Analysis of Regularized M-estimators in High-dimensions[END_REF][START_REF] Thrampoulidis | Regularized linear regression: A precise analysis of the estimation error[END_REF] which was previously used to quantify performance of regularized M-estimators such as the lasso [START_REF] Oymak | The Squared-Error of Generalized LASSO: A Precise Analysis[END_REF][START_REF] Thrampoulidis | Precise Error Analysis of Regularized M-estimators in High-dimensions[END_REF][START_REF] Thrampoulidis | Regularized linear regression: A precise analysis of the estimation error[END_REF]. Many technical ideas in [START_REF] Thrampoulidis | Precise Error Analysis of Regularized M-estimators in High-dimensions[END_REF][START_REF] Oymak | The Squared-Error of Generalized LASSO: A Precise Analysis[END_REF][START_REF] Thrampoulidis | Regularized linear regression: A precise analysis of the estimation error[END_REF] have been developed in earlier works. The CGMT can be seen as a descendant of Gordon's Gaussian min-max theorem [START_REF] Gordon | Some inequalities for Gaussian processes and applications[END_REF]. Rudelson and Vershynin [START_REF] Rudelson | On sparse reconstruction from fourier and gaussian measurements[END_REF] first recognized that Gordon's result (more precisely, its consequence known as escape through a mesh [START_REF] Gordon | On Milman's inequality and random subspaces which escape through a mesh in R n[END_REF]) is a useful theoretical device to study sparse regression. Ensuing papers by Stojnić [START_REF] Stojnic | Various thresholds for 1 -optimization in compressed sensing[END_REF][START_REF] Stojnic | A framework to characterize performance of LASSO algorithms[END_REF], Chandrasekaran et al. [START_REF] Chandrasekaran | Convex Graph Invariants[END_REF], Amelunxen et al. [START_REF] Amelunxen | Living on the edge: phase transitions in convex programs with random data[END_REF], Foygel and Mackey [START_REF] Foygel | Corrupted Sensing: Novel Guarantees for Separating Structured Signals[END_REF], and others, give sharper analyses and study more general settings. Their techniques percolated into the work by Thrampoulidis et al. [START_REF] Thrampoulidis | Precise Error Analysis of Regularized M-estimators in High-dimensions[END_REF] which we primarily refer to.

2. Frobenius Norms of Generalized Inverses. In this section we state our main results and prepare the proof. We first need to clear a technicality: for some A, spinv(A) will have multiple minimizers. This is, however, rare, as we prove in [START_REF] Dokmanic | Beyond moore-penrose part II: the sparse pseudoinverse[END_REF]: Theorem 2.1. Assume that A ∈ R m×n has columns in general position, and that A is in general position with respect to the canonical basis vectors e 1 , . . . , e m . Then the sparse pseudoinverse spinv(A) of A contains a single matrix whose columns are all exactly m-sparse.

Operationally, this means that for almost all matrices with respect to the Lebesgue measure on R m×n we will have a unique spinv, which simplifies the proofs. 3The importance of the Frobenius norm of a generalized inverse can be motivated by considering an overdetermined system of linear equations y = A x+z, where A ∈ C m×n has full row rank and Frobenius norm of a random element of ginv 0 (A) for A a random Gaussian matrix of size 20 × 30 (left) and a sparse pseudoinverse spinv(A) (generically in ginv 0 (A); cf. [START_REF] Dokmanic | Beyond moore-penrose part II: the sparse pseudoinverse[END_REF]) of the same matrix (right). The random element of ginv 0 (A) is computed by selecting m columns of A at random and inverting the obtained submatrix. The plot shows results of 5 identical experiments, each consisting of generating a random 20 × 30 matrix and computing the two inverses 100 times. In the first experiment, the outlier norms extend to 2000 so they were clipped at 100. Green lines denote medians, and boxes denote the second and the third quartile.

z is noise such that E{zz } ∝ I n . Then for W ∈ G(A) we have E z [ Wy -x 2 2 ] = E z [ Wz 2 2 ] ∝ W 2 F .
Thus the mean-squared error is controlled by the Frobenius norm of W and it is desirable to use generalized inverses with small Frobenius norms.

Note that for a rank-m A, the optimization (1.1) decouples over columns into m independent 0 problems. Even though such problems are in general NP-hard [START_REF] Davis | Adaptive Greedy Approximations[END_REF][START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF], Theorem 2.1 says that for a generic A ∈ R m×n with m < n, a sparsest generalized inverse has m 2 non-zeros. Thus a simple way to compute a sparsest generalized inverse (an element of ginv 0 (A)) is to invert any m × m submatrix of A and set the rest to zero. Unfortunately, this leads to poorly conditioned matrices, unlike computing the spinv as shown in Figure 2.1.

The goal of this section is to make the last statement quantitative by developing concentration results for the Frobenius norm of spinv(A) as well as ginv p (A) for 1 ≤ p ≤ 2 when A is an iid Gaussian random matrix.

Our results rely on the properties of the following geometric functional:

D(t) = D p (t; n) def = 1 n E h∼N (0,In) dist(h, • p * ≤ t) 2 , 1 ≤ p ≤ ∞, t ≥ 0, (2.2)
where dist(h, • p * ≤ t) def = min u: u p * ≤t hu 2 and 1/p + 1/p * = 1. In particular, Lemma B.4-Property 7 in Appendix B tells us that 0 < D(t) < 1 and for 0 < δ < 1, δ = D(t) -t 2 D (t) on (0, ∞) has a unique solution on (0, ∞), denoted t * = t * p (δ, n). With this notation we can state our main result. Theorem 2.2. Let A ∈ R m×n , 1 < m ≤ n, be a standard iid Gaussian matrix and

δ def = (m-1)/n ∈ (0, 1). For 1 ≤ p ≤ 2, define t * = t * p (δ, n) to be the unique solution of δ = D(t)-t 2 D (t) on (0, ∞) and denote α * = α * p (δ, n) def = D(t * ) δ(δ -D(t * ))
.

Assume there exist4 γ(δ) and N (δ) such that -t * D p (t * ; n) ≥ γ(δ) > 0 for all n ≥ N (δ). Then for any n ≥ max(2/(1 -δ), N (δ)) we have: for any 0 < ≤ 1,

(2.3) P n m ginv p (A) 2 F -(α * ) 2 ≥ (α * ) 2 ≤ n C 1 e -C2n 4 ,
where the constants C 1 , C 2 > 0 may depend on δ but not on n or .

From Theorem 2.2 we can derive more explicit results for the two most interesting cases: p = 1 and p = 2. For p = 2 we get a result about A † F complementary to a known large deviation bound [START_REF] Halko | Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[END_REF]Proposition A.5;Theorem A.6] obtained by a different technique.

Corollary 2.3 (p = 2). Let A ∈ R m×n , 1 < m ≤ n, be a standard iid Gaussian matrix, δ = (m -1)/n ∈ (0, 1), and α * = α * 2 (δ, n) def = D2(t * ;n) δ(δ-D2(t * ;n)) , with t * being the unique solution of δ = D 2 (t; n) -t 2 D 2 (t; n) on (0, ∞).
Then there exists N (δ) such that for n ≥ N (δ) we have: for any 0 < ≤ 1, (2.4)

P n m A † 2 F -(α * ) 2 ≥ (α * ) 2 ≤ n C 1 e -C2n 4 ,
where the constants C 1 , C 2 > 0 may depend on δ but not on n or , and

α * = α * 2 (δ; n) with (2.5) lim n→∞ α * 2 (δ; n) = 1/ √ 1 -δ.
We remark that Corollary 2.3 covers "small" deviations (0 < ≤ 1). In contrast, the result of [START_REF] Halko | Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[END_REF]

establishes 5 that E n m A † 2 F = n n-m-1 = 1
1-δ and that for any τ ≥ 1,

P n m A † 2 F ≥ 12n n-m τ ≤ 4τ -(n-m)/4 = 4e -n (1-m/n) log τ 4 .
For large n we have

12n n-m τ ≈ 12τ 1-δ ≈ 12τ (α * 2 ) 2 and (1-m/n) log τ 4 ≈ (1-δ) log τ 4
, hence this provides a bound for 1 + := 12τ ≥ 12 with an exponent log τ , of the order of log (instead of 4 we get for 0 < ≤ 1). Further, we also show that the probability of n m A † 2 F being much smaller than (α * ) 2 is exponentially small.

The most interesting corollary is for the sparse pseudoinverse, p = 1.

Corollary 2.4 (p = 1). With the notation analogous to Corollary 2.3, there exists N (δ) such that for all n ≥ N (δ) we have: for any 0 < ≤ 1, (2.6)

P n m spinv(A) 2 F -(α * ) 2 ≥ (α * ) 2 ≤ n C 1 e -C2n 4 ,
where the constants C 1 , C 2 > 0 may depend on δ but not on n or , and

α * = α * 1 (δ; n) with (2.7) lim n→∞ α * 1 (δ; n) = 2 π e - (t * 1 ) 2 2 t * 1 -δ(t * 1 ) 2 -1 -1 δ and t * 1 = √ 2 • erfc -1 (δ).
Proof of Corollaries The spinv and the MPP exhibit rather different qualitative behaviors. The Frobenius norm of the MPP monotonically decreases as δ gets smaller, while that of the spinv turns up below some critical δ. Intuitively, for small δ, the support of the spinv is concentrated on few entries which have to be comparably large to produce the diagonal in I = AX. A careful analysis of (2.7) using an asymptotic expansion of erfc(t) shows that for a sufficiently large n, α * 1 (δ; n) behaves as [δ log(1/δ)]

-1/2 when δ is small.

The bound (2.3) and the bounds in Corollaries 2.4 and 2.3 involve 4 instead of the more common 2 one gets for, e.g., Lipschitz functions: to guarantee a given probability in the right hand side of (2.3), should be of the order n -1/4 instead of the usual n -1/2 , suggesting a comparably higher variance of n m ginv p (A) F indeed concentrate and give a closed-form limiting value of the optimal α * . It would seem natural that an interpolation to p ∈ (1, 2) is possible, although α * p would be specified implicitly and computed numerically. It is less clear whether an extension to p > 2 is possible.

2.2.

A note on Gaussianity. Gaussian random matrices may appear as a serious restriction. It is known, however, that Gaussian matrices are a representative of a large class of random matrix models for which many relevant functionals are universal-they concentrate around the same value for a given matrix size [START_REF] Donoho | Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing[END_REF][START_REF] Oymak | Universality laws for randomized dimension reduction, with applications, Information and Inference[END_REF]. 7 Although it is tempting to justify our model choice by universality, in the case of sparse pseudoinverses we must proceed with care. As Oymak and Tropp point out [START_REF] Oymak | Universality laws for randomized dimension reduction, with applications, Information and Inference[END_REF], "... geometric functionals involving non-Euclidean norms need not exhibit universality." They give an example of 1 restricted minimum singular value. Indeed, as Figure 2.2 shows, while the predictions of Corollary 2.3 for the MPP remain true over a number of ensembles and thus seem to be universal, those of Corollary 2.4 for the spinv exhibit various levels of disagreement. For the Rademacher ensemble they collapse completely. In view of our results on pseudoinverses of structured matrices [START_REF] Dokmanic | Beyond moore-penrose part I: generalized inverses that minimize matrix norms[END_REF], this comes as no surprise since we know that in this case the spinv contains the MPP. Still, from Figure 2.2, results for Gaussian matrices are a good qualitative template for many absolutely continuous8 distributions, and the Gaussian assumption enables us to use sharp tools not available in a more general setting.

2.3.

A note on motivation. This work was originally motivated by a practical inverse problem in modern touchscreen technologies [START_REF] Piot | Optical touch tomography[END_REF]. The idea is as follows: an array of light-emitting diodes (LEDs) injects light into a glass panel. Disturbances in the light propagation caused by fingers are detected by photo diodes placed next to the LEDs. With many source-detector pairs, reconstructing the multiple touch locations becomes a tomographic problem. In order to meet the industry standards, the device must operate at a high refresh rate, yet it uses resource-constrained hardware. An obvious choice to solve the resulting over-constrained (due to coarse target resolution) tomographic problem is to apply the MPP of the forward matrix, but the refresh rate requirement precludes multiplication by a full matrix. This makes a sparse pseudoinverse attractive so long as it is stable, which translates to a controlled Frobenius norm. Even though the tomographic forward matrix is far from iid Gaussian (for example, it is sparse), it is interesting to compare it to the theoretical Gaussian results. As a toy model, we use a 15 × 15 pixel panel and randomly subsample the forward discrete Radon transform matrix to get a tall matrix of size (225/δ) × 225. We compute the ratio of the squared Frobenius norm of the spinv and the MPP and compare it to the ratio predicted by Corollaries 2.3 and 2.4 for Gaussian matrices. Results averaged over 10 realizations are shown in Table 2.1. While the two ratios are different, the Gaussian theory gives a good qualitative (and coarse quantitative) prediction. In general, we expect our results to be relevant whenever an application calls for multiplications by a precomputed, sparse pseudoinverse which is at the same time stable.

Proof of the Main Concentration

Result, Theorem 2.2. Our proof technique relies on decoupling the optimization for ginv p (A) over columns. A "standard" application of the CGMT would give an asymptotic result for the p norm of one column which holds in probability. However, because the squared Frobenius norm is a sum of m squared2 column norms, convergence in probability is not enough. To address this shortcoming we developed a number of technical results located mostly in Appendix B that lead to a stronger exponential concentration result which may be of independent interest to the users of the CGMT.

By definition, we have

ginv p (A) = arg min AX=I X p = arg min AX=I X p p ,
where we assume that the solution is unique. This is true by strict convexity for p > 1; for p = 1 it holds almost surely by Theorem 2.1. This optimization decouples over columns of X: denoting X * = ginv p (A) we have for the ith column that x * i = arg min Ax=ei x p . We can thus apply the following lemma proved in Section 3.1: Lemma 3.1. With notations and assumptions as in Theorem 2.2, we have for 0 < ≤ 1 and

n ≥ max(2/(1 -δ), N (δ)) P √ n x * 2 -α * ≥ α * ≤ 1 K 1 e -K2n 4 ,
where K 1 , K 2 > 0 may depend on δ but not on n or .

Lemma 3.1 tells us that √ n x * i 2 remains close to α * with high probability. To exploit the additivity of the squared Frobenius norms over columns we write (n

x * 2 2 -(α * ) 2 ) = ( √ n x * 2 - α * )( √ n x * 2 + α * ).
Then for any b > 0 we have that

P n x * 2 2 -(α * ) 2 ≥ (α * ) 2 ≤ P √ n x * 2 -(α * ) ≥ (α * ) 2 /b + P ( √ n x * 2 + α * ) ≥ b .
By taking b = 3α * , we bound both terms using Lemma 3.1 to obtain

P n x * 2 2 -(α * ) 2 ≥ (α * ) 2 ≤ 3 K 1 e -K2n( /3) 4 + 1 K 1 e -K2n ≤ 1 C 1 e -C2n 4
with an appropriate choice of C 1 , C 2 . This characterizes the squared 2 norm of one column of the MPP. The (scaled) squared Frobenius norm of X * is a sum of m such terms which are not independent, n m

X * 2 F = n m m i=1 x * i 2 2
, and we want to show that it stays close to (α * ) 2 . We work as follows:

P n m X * 2 F -(α * ) 2 ≥ (α * ) 2 = P m i=1 n x * i 2 2 -(α * ) 2 ≥ m (α * ) 2 ≤ P m i=1 n x * i
If the sum of m terms is to be larger than m , then at least one term must be larger than ,

( * ) ≤ P ∃ i, 1 ≤ i ≤ m : n x * i 2 2 -(α * ) 2 ≥ (α * ) 2 = P m i=1 n x * i 2 2 -(α * ) 2 ≥ (α * ) 2 ≤ m i=1 P n x * i 2 2 -(α * ) 2 ≥ (α * ) 2 ≤ m 1 C 1 e -C2n 4 ≤ δn C 1 e -C2n
L def = n max(1/p-1/2,0) ), if we choose λ ≤ √ n- √ m L ( 1
-), minimizers x * and x of (3.8) and (3.9) coincide9 with probability at least 1 -e -2 (

√ n- √ m) 2 /2 . Using y 2 = max u: u 2 ≤1 u y we get (3.10) x = arg min x max u: u 2 ≤1 u Ax + λ x p -u e 1 .
The objective in (3.10) is a sum of a bilinear term involving A and a convex-concave function10 ψ(x, u) = λ x p -u e 1 as required by the CGMT (Appendix A.2). The CGMT requires x to belong to a compact set so instead of (3.10) we analyze the following bounded modification:

(3.11) x K = arg min x: x 2 ≤K max u: u 2 ≤1
u Ax + λ x p -u e 1 .

We will see that x K = x with high probability as soon as K is large enough. Part (ii) of the CGMT says that the random optimal value of the principal optimization (3.11) concentrates if the random value of the following auxiliary optimization concentrates:

(3.12) xK = arg min x: x 2 ≤K max u: u 2 ≤1 x 2 g u -u 2 h x + λ x p -u e 1 ,
where g ∼ (0, I m ) and h ∼ (0, I n ) are independent. This lets us prove that if the norm xK 2 of the optimizer of (3.12) concentrates, then the norm x K 2 of the optimizer of (3.11) concentrates around the same value. 11We now go through a series of steps to simplify (3.12). For convenience we let z be a scaled version of x, z = x √ n (accordingly

A = K √ n).
Using the variational characterization of the p norm we rewrite (3.12) as (3.13) ẑA = arg min

z: z 2 ≤A max β:0≤β≤1 u: u 2 =β w: w p * ≤1 1/ √ n • z 2 g u -1/ √ n • u 2 h z -u e 1 + λ/ √ n • w z.
Let žA be a (random) value of z at the optimum of the following reordered optimization:

(3.14) max β:0≤β≤1 w: w p * ≤1 min z: z 2 ≤A max u: u 2 =β 1/ √ n • z 2 g u -1/ √ n • u 2 h z -u e 1 + λ/ √ n • w z.
By Lemma B.11 and Lemma B.12, žA 2 and ẑA 2 stay close with high probability (this will be made precise below). We simplify (3.14) further as follows:

(3.14) = max

β:0≤β≤1 w: w p * ≤1 min z: z 2 ≤A β z 2 g/ √ n -e 1 2 -β/ √ n • h z + λ/ √ n • w z (3.15) = max β:0≤β≤1 w: w p * ≤1 min α:0≤α≤A min z: z 2 =α β z 2 g/ √ n -e 1 2 -β/ √ n • h z + λ/ √ n • w z = max β:0≤β≤1 w: w p * ≤1 min α:0≤α≤A β αg/ √ n -e 1 2 -α/ √ n • βh -λw 2 .
The objective in the last line is convex in α and jointly concave in (β, w), and the constraint sets are all convex and bounded, so by [START_REF] Sion | On General Minimax Theorems[END_REF]Corollary 3.3] we can again exchange min and max:

= min α:0≤α≤A max β:0≤β≤1 w: w p * ≤1 β αg/ √ n -e 1 2 -α/ √ n • βh -λw 2 = min α:0≤α≤A max β:0≤β≤1 β αg/ √ n -e 1 2 -α/ √ n • min w: w p * ≤1 βh -λw 2 = min α:0≤α≤A max β:0≤β≤1 φ(α, β; g, h), (3.16)
where (3.17) φ(α, β; g, h)

def = β αg/ √ n -e 1 2 -α/ √ n • dist(βh, • p * ≤ λ).
We thus simplified a high-dimensional vector optimization (3.9) into an optimization over two scalars (3.16), one of these scalars, α, almost giving us what we seek-the (scaled) 2 norm of x.

To put the pieces together, there now remains to formally prove that the min-max switches and the concentration results we mentioned actually hold.

3.2. Combining the ingredients. By Lemma B.2, φ(α, β; g, h) concentrates around some deterministic function κ(α, β) = κ p (α, β; n, δ, λ) with δ = (m -1)/n. By Lemma B.8-3, (3.18) arg min

α:0≤α≤A max β:0≤β≤1 κ(α, β) = α * = α * p (δ; n) def = D p (t * p ; n) δ(δ -D p (t * p ; n)) as soon as A = K √ n > α * and λ ≤ t * , with t * = t * p (δ, n) defined in Lemma B.4-Property 7. By Lemma B.10, for 0 < ≤ max(α * , A -α * ), the minimizer α * φ def = arg min 0≤α≤A max 0≤β≤1 φ(α, β; g, h)
stays -close to α * with high probability:

P{|α * φ -α * | ≥ } ≤ ζ n, ω( ) 2 , with ζ(n, ξ) = ζ(n, ξ; A, δ) def = c1 ξ e -c2ξ 2 n•c(δ,A) , c(δ, A) def = min(δ,A -2 ) 1+δA 2 , c 1 , c 2 universal constants, and ω( ) = ω p ( ; n, δ, λ) def = 2 2 λδ/t * (1 + δ(α * + ) 2 ) 3/2 .
As a consequence, by Lemma B.12, the scaled norm √ n x K 2 of the minimizer of the (bounded)

principal optimization problem (3.11) stays close to α * with high probability,

P √ n x K 2 -α * ≥ ≤ 4ζ n, ω( ) 2 .
Similarly, for 0 < ≤ min(α * , Aα * ) by invoking Lemma B. [START_REF] Foygel | Corrupted Sensing: Novel Guarantees for Separating Structured Signals[END_REF] we have that the norm √ n x of the minimizer of the unbounded optimization (3.10) stays close to α * with high probability

P √ n x 2 -α * ≥ ≤ 4ζ n, ω( ) 2 ,
and in fact

P[ x = x K ] ≤ 4ζ n, ω( ) 2 .
Since the p norm is L-Lipschitz with respect to the Euclidean metric in R n , with L = n max(1/p-1/2,0) , Lemma B.1 gives for any λ < λ max (n, m, t * )

def = min √ n- √ m

2L

, t * that the minimizer x * of the equality-constrained optimization (3.8) coincides with the minimizer x of the lasso formulation (3.9)-(3.10) except with probability at most e -n(1-

√ δ+1/n) 2 /8 . Overall then, for λ < λ max and ≤ min(α * , A -α * ), (3.19) P √ n x * 2 -α * ≥ ≤ e -n(1- √ δ+1/n) 2 /8 + 4ζ n, ω( ) 2 .
The infimum over admissible values of λ is obtained by taking its value when λ = λ max . δ to denote inequalities up to a constant that may depend on δ, but not on n or , provided n ≥ N (δ). We specify N (δ) where appropriate.

By Lemma B.5-item 1, for any 1 ≤ p ≤ 2 and any n ≥ 1,

λ max = t * min √ n- √ m n 1/p-1/2 1 2t * , 1 δ t * min √ n(1- √ m/n) n 1/p-1/2 1 n 1-1/p , 1 = t * min 1 -m/n, 1 . For n ≥ 2 1-δ we have 1 -m/n = 1 -δ + 1 n ≥ 1 -(1 + δ)/2 δ 1, hence λ max δ t * . With the shorthands D(t) = D p (t; n) and D = D p (t * ; n), we have 1 + δ(α * + ) 2 ≤ 1 + δA 2 ≤ 4(1 + δ(α * ) 2 ) = 4(1 + D δ-D ) = 4δ δ -D δ (δ -D) -1 , hence with λ = λ max we get for n ≥ 2/(1 -δ), ω( ) = 2 2 λ max t * δ(α * ) 2 (1 + δ(α * + ) 2 ) 3/2 δ 2 D δ-D ( 4δ δ-D ) 3/2 δ 2 D √ δ -D .
By Lemma B.5-4 we have

D = D p (t * ; n) ≥ (δ/C) 2 for a universal constant C independent of n or p, hence for n ≥ 1, D δ 1 and for n ≥ 2/(1 -δ), ω( ) δ -t * D p (t * ; n) 2 .
Moreover since min(δ, A -2 ) ≥ 1 4 min(δ, (α * ) -2 ) = 1 4 min(δ, δ(δ -D)/D) we also get

c(δ, A) = min(δ,A -2 ) 1+δA 2 ≥ min(δ,δ(δ-D)/D) δ/(δ-D) = min(δ -D, (δ-D) 2 D ) ≥ (δ -D) 2 = 1 4 [-t * D p (t * ; n)] 2 .
Since -t * D p (t * ; n) ≥ γ(δ) > 0 for any n ≥ N (δ) (recall that t * = t * p (δ; n)), we have

(3.20) -t * D p (t * ) δ 1,
and we obtain for n ≥ max(2/(1 -δ), N ): ω( ) δ 2 and c(δ, A) δ 1. Combining the above yields, for 0 < ≤ 1, n ≥ max(2/(1 -δ), N (δ)):

P x * -α * √ n ≥ α * √ n ≤ e -C1n + 4ζ n, C 2 2 ≤ 1 K 1 ( ) 2 e -K2( ) 4 n with K i , C i δ 1.

Conclusion.

We studied the concentration of the Frobenius norm of p -minimal pseudoinverses for iid Gaussian matrices. In addition to a general result for 1 ≤ p ≤ 2, we gave explicit bounds for p ∈ {1, 2}, that is, for the sparse pseudoinverse and the Moore-Penrose pseudoinverse. Our results show that for a large range of m/n the Frobenius norm of the spinv is close to the Frobenius norm of the MPP which is the best possible among all generalized inverses (Figure 2.2). The same does not hold for the various ad hoc strategies that yield generalized inverses with the same non-zero count (Figure 2.1). In applications, this means that the spinv will not blow up noise much more than the MPP. Important future directions are extensions of Theorem 2.2 to matrix norms other than p with 1 ≤ p ≤ 2, as well as matrix models other than iid Gaussian.

5.

Acknowledgments. The authors would like to thank Mihailo Kolundžija, Miki Elad, Jakob Lemvig, and Martin Vetterli for the discussions and input in preparing this manuscript. A special thanks goes to Christos Thrampoulidis for his help in understanding and applying the Gaussian min-max theorem, and to Simon Foucart for discussions leading to the proof of [ Lemma A.1. Let h be a standard Gaussian random vector of length n, h ∼ N (0, I n ), and f : R n → R a 1-Lipschitz function. Then the following hold:

(a) For any 0 < < 1, P{ h for all |λ| ≤

2 2 ≤ n(1 -)} ≤ e -2 n/4 ; P{ h 2 2 ≥ n/(1 -)} ≤ e -2 n/4 ; (b) For any 0 < < 1, P h 2 2 / ∈ [(1 -)n, n/(1 -)] ≤ 2e - 2 n 4 ; (c) For any > 0, P h 2 2 -n ≥ √ n ≤ 2e -8 for 0 ≤ ≤ n, 2e - √ n 8 for > n; (d) For any u > 0, P {f (h) -Ef (h) ≥ u} ≤ e -u 2 /2 ; P {f (h) -Ef (h) ≤ -u} ≤ e -u 2 /2 ; (e) For any u > 0, P{|f (h) -Ef (h)| ≥ u} ≤ 2e -u 2 /2 ; (f ) Var{f (h)} ≤ 1.
Var{f (h)} ≤ E{ ∇f (h) 2 2 } for 1-Lipschitz f for which ∇f (h) 2 ≤ 1.
We will also use the following facts which can be verified by direct computation:

Lemma A.2. Let θ(t) def = E(|h| -t) 2
+ , where h ∼ N (0, 1) and t ≥ 0. Then

1. θ(t) = t 2 + 1 erfc t √ 2 -2 π e -t 2 2 t, 2. θ(t) -(t/2)θ (t) = erfc(t/ √ 2).
A.2. Convex Gaussian Min-Max Theorem (CGMT). Let the principal optimization (PO) and auxiliary optimization (AO) be defined as

Φ(G) def = min v∈Sv max u∈Su u Gw + ψ(v, u), (PO) φ(g, h) def = min v∈Sv max u∈Su v 2 g u + u 2 h v + ψ(v, u), (AO) with G ∈ R m×n , g ∈ R m , h ∈ R n , S v ⊂ R n , S u ⊂ R m and ψ : R n × R m → R.
Then we have the following result.

Theorem A.3. [31, Theorem 6.1] In (PO) and (AO), let S v and S u be compact and ψ continuous on S v × S u . Let also G, g, h have iid standard normal entries. Then the following hold:

(i) For all c ∈ R P{Φ(G) < c} ≤ 2P{φ(g, h) ≤ c}.
(ii) If ψ(v, u) is additionally convex-concave on S v × S u where S v and S u are convex, then for all c ∈ R P{Φ(G) > c} ≤ 2P{φ(g, h) ≥ c}.

In particular, for all µ ∈ R and t > 0, P{|Φ(G) -µ| > t} ≤ 2P{|φ(g, h) -µ| ≥ t}.

Appendix B. Lemmata for Section 3.

Lemma B.1 ([22, Lemma 9.2] with explicit dependence on ). Let A ∈ R m×n be a random matrix with iid standard normal entries, and m < n. Let further y ∈ R m and consider the solution of an 2 -lasso with a regularizer f which is L-Lipschitz with respect to the 2 -norm:

x def = arg min x∈R n y -Ax 2 + λf (x).
Then for any 0 ≤ < 1 and 0

< λ < √ n- √ m L (1 -) we have y = Ax with probability at least 1-e -2 ( √ n- √ m) 2 /2 ,
(A )/( √ n - √ m) ≤ 1 -] ≤ e -2 ( √ n- √ m) 2 /2 .
Let p def = y -Ax and w def = A † p, where A † = A (AA ) -1 denotes the MPP (AA is almost surely invertible). Since w

2 2 = p (AA ) -1 p ≤ p 2 2 σ -2
min (A ) we have from (B.21) that for any 0 < < 1, with probability at least 1 -e -2 (

√ n- √ m) 2 /2 , w 2 ≤ p 2 ( √ n- √ m)(1-) . Let x • def = x + w so that y -Ax • = 0. Optimality of x gives (B.22) ( * ) = y -Ax 2 + λf (x ) -y -Ax • 2 + λf (x • ) ≤ 0. On the other hand, ( * ) = p 2 + λf (x ) -λf (x • ) ≥ p 2 -λL x -x • 2 = p 2 -λL w 2 ≥ p 2 1 - λL ( √ n- √ m)(1-) ,
where, by (B.22), the last expression must be non-positive. But if we choose λ <

√ n- √ m L ( 1
-), the only way to make it non-positive is that p 2 = 0.

Lemma B.2. Let g ∼ N (0, I m ), h ∼ N (0, I n ), 1 ≤ p ≤ ∞, and define ∆ p (β; h, λ) def = 1 √ n dist(βh, • p * ≤ λ) and ∆ p (β; n, λ) def = E[∆ p (β; h, λ)].
There exist universal constants c 1 , c 2 > 0 such that for any 0 < < 2, any integers m, n and any A > 0 we have, with δ def = (m -1)/n and φ(α, β; g, h) defined as in (3.17):

P ∃0 < α ≤ A, 0 < β < 1, |φ(α, β; g, h) -κ(α, β)| ≥ ≤ c1 e -c2 2 n• min(δ,1/A 2 ) 1+δA 2 def = ζ(n, ; A, δ),
where

(B.23) κ(α, β) = κ p (α, β; n, δ, λ) def = β δα 2 + 1 -α∆ p (β; n, λ).
Proof. We first look at the term αg/ √ ne 1 2 . Partitioning g as [g 0 , g ] ,

g ∈ R m-1 , αg/ √ n -e 1 2 2 = α g/ √ n 2 2 + (αg 0 / √ n -1) 2 .
Using Lemma A.1(b) we get for the first term:

P ∃0 < α ≤ A, α g/ √ n 2 2 / ∈ [(1 -)δα 2 , δα 2 /(1 -)] ≤ 2e - 2 (m-1) 4 = 2e - 2 nδ 4 ,
since the event { α g/ √ n / ∈ [(1 -)δα 2 , δα 2 /(1 -)]} does not depend on α > 0. Next, we show that the term (αg 0 / √ n -1) 2 cannot deviate much from 1: setting = /2,

we have √ 1 -< 1 -and 1 + < 1/ √ 1 -hence P ∀0 < α ≤ A, αg0 √ n -1 2 ∈ [1 -, 1/(1 -)] ≥ P ∀0 < α ≤ A, αg0 √ n -1 ∈ [1 -, 1 + ] ≥ P ∀0 < α ≤ A, αg 0 / √ n ∈ [-, ] = P Ag 0 / √ n ∈ [-, ] .
Then, with erfc being the complementary error function and using erfc(z) ≤ exp(-z 2 ) [6],

P ∃0 < α ≤ A, αg0 √ n -1 2 / ∈ [1 -, 1/(1 -)] ≤ P(|g 0 | > √ n A ) = erfc √ n √ 2A ≤ e - 2 n 2A 2 = e - 2 n 8A 2 .
Combining the above, we get that: for any 0 [START_REF] Perraudin | Designing Gabor Windows Using Convex Optimization[END_REF] where the constants c 1 , c 2 are universal.

< < 1, setting = 1 -(1 -) 2 = (2 -) ≥ , P ∃0 < α ≤ A, αg/ √ n -e 1 2 / ∈ [(1 -) δα 2 + 1, δα 2 + 1/(1 -)] = P ∃0 < α ≤ A, αg/ √ n -e 1 2 2 / ∈ [(1 -)(δα 2 + 1), (δα 2 + 1)/(1 -)] ≤ 2e - 2 nδ 4 + e - 2 n 8A 2 ≤ c 1 e -c 2 2 n•min(δ,1/A 2 ) ≤ c 1 e -c 2 2 n•min(δ,1/A 2 ) , (B.
For the second term in φ(α, β; g, h), we note that Euclidean distance to a convex set dist(x, C) is 1-Lipschitz in x with respect to • 2 so by Lemma A.1(e) we get for 0 < β ≤ 1 (we omit the dependency in λ for brevity) and any τ ≥ 0 that (B.25)

P {|∆ p (β; h) -∆ p (β)| > τ } ≤ 2e - τ 2 n 2β 2 ≤ 2e -τ 2 n 2 .
This obviously extends to β = 0 since ∆ p (0; h) = ∆ p (0) = 0. Next, we want to bound

P {∃β ∈ [0, 1], |∆ p (β; h) -∆ p (β)| > τ } = P sup β∈[0,1] |∆ p (β; h) -∆ p (β)| > τ .
By Lemma B.14, the function

β → f h (β) def = |∆ p (β; h) -∆ p (β)| is L h -Lipschitz in β with L h def = max { h 2 /
√ n, 1}. Hence f h is continuous, and its supremum on the closed interval [0, 1] is indeed a maximum reached at some maximizer β h . Let b ≤ 1/2 and Y b = {bτ /2, 3bτ /2, . . . , (k -1/2)bτ } be a uniform sampling of [0, 1] with spacing bτ , with the last segment possibly being shorter. For a given h, there exists y h ∈ Y b such that |β h -y h | ≤ bτ . For this y h we write

f h (β h ) -f h (y h ) ≤ |f h (β h ) -f h (y h )| ≤ L h |β h -y h | ≤ L h bτ, so that P{ sup β∈[0,1] f h (β) > τ } = P{f h (β h ) > τ } ≤ P{f h (y h ) + L h bτ > τ } ≤ P {f h (y h ) > τ /2 or L h bτ > τ /2} ≤ P{f h (y h ) > τ /2} + P{max h 2 / √ n, 1 b > 1/2}.
As we do not know a priori to which y ∈ Y b the maximizer β h will be close, we continue with a union bound, and we further use that b ≤ 1/2 to obtain by (B.25) and Lemma A.1(a)

P{ sup β∈[0,1] f h (β) > τ } ≤ P ∃y ∈ Y b , f h (y) > τ /2 + P h 2 2 > n 4b 2 ≤ |Y b | 2e -τ 2 n 8 + e -(1-4b 2 ) 2 n 4 ≤ (1 + 1/(bτ ))2e -τ 2 n 8 + e -(1-4b 2 ) 2 n 4 . Setting b def = 1 2 2- √ 2 2
≈ 0.27 we get that for any 0 < τ < 1 we have

(1-4b 2 ) 2 4 = 1 8 ≥ τ 2 8 , hence (B.26) P{ sup β∈[0,1] f h (β) > τ } ≤ (3 + 2/(bτ ))e -τ 2 n 8 < 11 τ e -τ 2 n 8 , 0 < τ < 1.
To conclude we combine concentration bounds for both terms. First, we observe that sup

0≤α≤A 0≤β≤1 |φ(α, β; g, h) -κ(α, β)| ≤ sup 0≤α≤A αg √ n -e 1 2 -1 + δα 2 + A sup 0≤β≤1 |∆ p (β; h) -∆ p (β)|
and by a union bound we just need to control the probability that each term exceeds /2. Since we assume that 0 < < 2, we can use the multiplicative control (B.24) as follows:

P ∃α ∈ (0, A], αg √ n -e 1 2 -δα 2 + 1 > 2 = P    ∃α ∈ (0, A], αg √ n -e1 2 √ δα 2 +1 -1 > 2 √ δα 2 +1    ≤ P    ∃α ∈ (0, A], αg √ n -e1 2 √ δα 2 +1 -1 > 2 √ δA 2 +1    ≤ P ∃α ∈ (0, A], αg/ √ n-e1 2 √ δα 2 +1 / ∈ [1 -, 1 1-] ≤ c 1 e -c 2 2 n•min(δ,1/A 2 ) . provided that [1 -, 1/(1 -)] ⊂ [1 -2 √ δA 2 +1 , 1 + 2 √ δA 2 +1
]. This is achieved with =

/(1 + √ δA 2 +
φ S = inf α∈S φ(α) ≤ inf α∈S [κ(α) + ] = κ S + , (B.29) φ S = inf α∈S φ(α) ≥ inf α∈S [κ(α) -] = κ S -. (B.30)
We will shortly characterize κ(α, β) and κ(α) using properties of the following quantity:

(B.31) D p (t; n) def = E[ 1 √ n dist(h, • p * ≤ t)] 2 . Lemma B.4 (Deterministic properties of D p ). Let t ≥ 0, 1 ≤ p ≤ ∞,
E[dist(h, C t )] = b∈S n-1 ∞ r=t/ √ n dist(rb, C t ) p h (rb) µ(db) r n-1 dr ≤ b∈S n-1 ∞ r=t/ √ n r p h (rb) µ(db) r n-1 dr = Z n µ(S n-1 ) ∞ r=t/ √ n
r n e -r 2 /2 dr, where Z n = (2π) -n/2 , µ(S n-1 ) = 2π n/2 /Γ n 2 , and Γ (•) being the gamma function. The last expression vanishes as t → ∞. 5. The upper bound follows from Property 3 and Jensen's inequality. To get the lower bound we compute nD p (0) = [E h 2 ] 2 by integration in polar coordinates,

E{dist(h, C 0 )} = E{ h 2 } = b∈S n-1 ∞ r=0 r p h (rb) µ(db) r n-1 dr = Z n µ(S n-1 ) ∞ r=0 r n e -r 2 /2 dr (a) = (2π) -n/2 2π n/2 Γ n 2 ∞ s=0 2 n-1 2 s n-1 2 e -s dr (b) = √ 2 Γ n + 1 2 Γ n 2 ,
where in (a) we used the substitution u = r 2 /2, and in (b) we invoked the definition of the gamma function, Γ(z) = ∞ 0 x z-1 e -x dx. We now use the inequality of Wendel, [36, Eq. ( 7)], Γ(x + a) Γ(x) ≥ x(x + a) a-1 to conclude that

(B.32) E{ h 2 } ≥ n(n + 1) -1/2
and D p (0) ≥ n/(n + 1).

6. Using dist(h, C t ) = tdist(h/t, C 1 ) and a change of variable r = tρ we obtain:

q(t) def = nD p (t) = Z n t n+1 b∈S n-1 ∞ ρ=0 dist(ρb, C 1 )e -ρ 2 t 2 /2 µ(db)ρ n-1 dρ (B.33)
so that D p (t) is infinitely differentiable (by the dominated convergence theorem).

7. In particular, as ∂ ∂t dist(ρb, C 1 )e -ρ 2 t 2 /2 ρ n-1 = dist(ρb, C 1 )tρ n+1 e -ρ 2 t 2 /2 ≤ ρ n+2 te -ρ 2 t 2 /2 where the rightmost expression is integrable for every t > 0 and n ∈ N, we can differentiate under the integral sign in (B.33) to get

-t 2 D p (t) = -t n q(t)q (t) = -1 n q(t) (n + 1)q(t) -Z n t n+3 S n-1 ∞ 0 dist(ρb, C 1 )ρ n+1 e -ρ 2 t 2 /2 µ(db) dρ . (B.34)
All terms can be seen to vanish as t → ∞ by arguments analogous to those in the end of the proof of Property 4, hence lim t→∞ [-t 2 D p (t)] = 0. Since D p (t) is strictly decreasing we have D p (t) < 0. Since it is convex, D p (t) ≥ 0. Thus

g (t) = D p (t) -1 2 D p (t) -t 2 D p (t) = 1 2 D p (t) -t 2 D p (t) < 0
for t > 0, meaning that g(t) is strictly decreasing. Since lim t→∞ [-t 2 D p (t)] = 0 and lim t→∞ D p (t) = 0, we have lim t→∞ g(t) = 0. It follows that for 0 < δ < lim t→0 g(t), there is a unique t * (δ), such that 0 < t * (δ) < ∞ and g(t) > δ for t < t * and g(t) < δ for t > t * . Finally, since g(t) ≥ D p (t) we have lim t→0 g(t) ≥ D p (0).

Lemma B.5. Denote (B.35) θ(t) def = E(|h| -t) 2 + ,
with h being a standard normal variable and ( • ) + = max( • , 0) the positive part. This is a strictly decreasing function of t with θ(0) = 1 and lim t→∞ θ(t) = 0. Recalling that t * p (δ; n) is the unique solution to D p (t; n) -t 2 D p (t; n) = δ on (0, ∞), the following holds for all 1 ≤ p ≤ ∞, 0 < δ < 1:

1. For any n ≥ 1, (B.36) t * p (δ; n) ≤ 2 θ -1 (δ) n 1-1/p . 2. For any n ≥ 2 1-δ , (B.37) t * p (δ; n) ≥ θ -1 ( 1+δ 2 ) > 0. 3. For any n ≥ max 2 1-δ , 1 δ , (B.38) t * p (δ; n) ≥ max θ -1 (2δ), θ -1 ( 1+δ 2 ) > 0.
4. There is a universal constant C independent of δ, p and n such that for all n ≥ 1 we have

(B.39) D p (t * p ; n) ≥ (δ/C) 2 ,
where we use the shorthand t * p = t * p (δ; n).

Lemma B.6. With the notations of Theorem 2.2, for p = 2,

(B.40) lim n→∞ -t * 2 D 2 (t * 2 ; n) = (1 -δ)δ > 0, lim n→∞ α * 2 (δ; n) = 1 √ 1-δ .
Lemma B.7. With the notations of Theorem 2.2 for p = 1, denoting t * 1 (δ

) def = √ 2 • erfc -1 (δ), lim n→∞ -t * 1 D 1 (t * 1 ; n) > 0, α * 1 (δ) def = lim n→∞ α * 1 (δ; n) = 2 π e - (t * 1 ) 2 2 t * 1 -δ(t * 1 ) 2 -1 -1 δ .
Proof of Lemmata B.5-B.6-B.7.

• Step 1. We show that for all p, n, t we have

(B.41) D p (t; n) ≥ D 1 (t; n) ≥ D p tn 1-1/p ; n .
The inequalities

• p * ≥ • ∞ ≥ n -1/p * • p * = n -(1-1/p) • p * imply C t,p ⊂ C t,1 ⊂ C tn 1-1/p ,p . It follows that d(•, C t,p ) ≥ d(•, C t,1 ) ≥ d(•, C tn 1-1/p ,
) def = 1 n E dist 2 (h, • p * ≤ t)
. By Jensen's inequality, for any p, n, t:

(B.45) D p (t; n) = 1 n E dist(h, • p * ≤ t) 2 ≤ 1 n E dist 2 (h, • p * ≤ t) = Dp (t; n). For p = 1, p * = ∞ we compute D1 (t) def = 1 n E dist 2 (h, • ∞ ≤ t) = 1 n E h -proj • ∞ ≤t h 2 2 = 1 n n i=1 E(|h i | -t) 2 + = θ(t).
(B.46)

• Step 4. We get (B.36) by combining the previous steps. For any p, δ, n:

θ(t * p n 1/p-1 /2) (B.46) = D1 (t * p n 1/p-1 /2) (B.45) ≥ D 1 (t * p n 1/p-1 /2) (B.41) ≥ D p (t * p /2) (B.42) ≥ δ. • Step 5. Since the function f : h → f (h) def = dist(h, • p * ≤ t
) is 1-Lipschitz, and h standard normal, we can apply Lemma A.1(f) to show that for any p, n, t,

(B.47) D p (t; n) ≥ Dp (t; n) -1 n .
• Step 6. Combining with the previous steps yields for any p, δ, and n > 1 1-δ :

θ(t * p ) (B.46) = D1 (t * p ) (B.47) ≤ D 1 (t * p ) + 1 n (B.41) ≤ D p (t * p ) + 1 n (B.43) ≤ δ + 1 n < 1.
For n ≥ 2 1-δ , we have δ +

D p (t) -t 2 D p (t) = q(t) n E[dist(h, C t )( h 2 2 -n)].
Observing further that E[ h 2 2

n] = 0 and E[dist(h, C t )] = q(t), the following holds:

D p (t) -t 2 D p (t) = q(t) n E (dist(h, C t ) -q(t))( h 2 2 -n) ≤ D p (t) E dist(h, C t ) -q(t) h 2 2 -n √ n = D p (t) ∞ 0 P dist(h, C t ) -q(t) h 2 2 -n √ n ≥ d .
The integrand can be controlled by a union bound as

P dist(h, C t ) -q(t) h 2 2 -n √ n ≥ ≤ P dist(h, C t )-q(t) ≥ √ +P h 2 2 -n √ n ≥ √
which together with Lemma A.1(e) for the first term and Lemma A.

d def = C < ∞. • Step 8. (Proof of Lemma B.6). Since dist(h, • 2 ≤ t) = ( h 2 -t) + , we have D 2 (t; n) = 1 n (E( h 2 -t) + ) 2 . With d(t) def = D 2 (t; n) = 1 √ n E( h 2 -t) + we have d (t) = -1 √ n E[I h 2 >t ] = -1 √ n P( h 2 > t) and -(t/2)D 2 (t) = -td(t)d (t). With a change of variables τ = t/ √ n, define F (τ ; n) def = F 1 (τ ; n) + F 2 (τ ; n) with F 1 (τ ; n) def = D 2 (τ √ n; n) = E h 2 √ n -τ + 2 , F 2 (τ ; n) def = -τ √ n 2 D 2 (τ √ n; n) = E h 2 √ n -τ + • τ P h 2 √ n > τ .
Since h 2 concentrates around √ n for large n, we show below that for any 0 < τ < 1,

(B.50) lim n→∞ F 1 (τ ; n) def = F 1 (τ ) = (1 -τ ) 2 and lim n→∞ F 2 (τ ; n) def = F 2 (τ ) = (1 -τ )τ.
It follows that for δ ∈ (0, 1) we have lim n→∞ F (1 -δ; n) = δ and

lim n→∞ t * 2 (δ;n) √ n = 1 -δ, lim n→∞ -(t * 2 /2)D 2 (t * 2 ; n) = F 2 (δ) = (1 -δ)δ, lim n→∞ D(t * 2 ; n) = F 1 (δ) = δ 2 , lim n→∞ α * 2 (δ; n) = δ 2 δ(δ-δ 2 ) = 1/ √ 1 -δ.
which establishes (B.40).

To prove (B.50) we compute as follows for 0 < τ < 1 and > 0:

E h 2 / √ n -τ + = E h 2 / √ n -τ + h 2 / √ n -1 > P h 2 / √ n -1 > + E ( h 2 / √ n -τ ) + h 2 / √ n -1 ≤ P h 2 / √ n -1 ≤ , P h 2 / √ n > τ = P h 2 / √ n > τ h 2 / √ n -1 > P h 2 / √ n -1 > + P h 2 / √ n > τ h 2 / √ n -1 ≤ P h 2 / √ n -1 ≤ .
For any 0 < < min(1 -τ, 1 2 ) we get

P h 2 / √ n -1 ≤ (a) ≥ 1 -2e -cn 2 , P h 2 / √ n > τ h 2 / √ n -1 ≤ = 1, E h 2 / √ n -τ + ≥ (1 -τ -)(1 -2e -cn 2 ), P h 2 / √ n > τ ≥ 1 -2e -cn 2 , E h 2 / √ n -τ + h 2 / √ n -1 ≤ ≥ 1 -τ -> 0,
where (a) follows from Lemma A.1(b) by noting that for 0 < ≤ 1 2 , 1/(1 -) ≤ 1 + . Hence, with = (1 -τ )/n 1/4 ,

F 1 (τ ; n) ≥ (1 -τ ) 2 (1 -n -1/4 ) 2 (1 -2e -c(1-τ ) 2 n 1/2 ) 2 , (B.51) F 2 (τ ; n) ≥ τ (1 -τ )(1 -n -1/4 )(1 -2e -c(1-τ ) 2 n 1/2 ) 2 . (B.52) For an upper bound, let c n def = 1 √ n E h 2 . Since n √ n+1 (B.32) ≤ E h 2 ≤ √ n we have 1 ≥ c n ≥ n n+1 ≥ 1 -1 2n ⇒ 0 ≤ 2(1 -c n ) ≤ 1/n. By Jensen's inequality, for 0 < τ < 1, E h 2 √ n -τ + ≤ E h 2 √ n -τ 2 + ≤ E h 2 √ n -τ 2 = 1 -2c n τ + τ 2 = (1 -τ ) 2 + 2(1 -c n )τ ≤ (1 -τ ) 2 + τ /n = (1 -τ ) 1 + τ (1-τ ) 2 n , so that F 1 (τ ; n) ≤ (1 -τ ) 2 + τ /n and F 2 (τ ; n) ≤ τ (1 -τ ) 1 + τ (1-τ ) 2 n ≤ τ (1 - τ ) 1 + τ (1-τ )
0 < t min (δ) def = θ -1 ( 1+δ 2 ) ≤ t * 1 (δ; n) ≤ 2θ -1 (δ) def = t max (δ).
By the continuity and strict monotonicity of θ, V (δ)

def = inf t∈[tmin(δ),tmax(δ)] {θ(t) -θ(2t)} > 0. By the convexity of D 1 (t) with h = t = t * 1 we get D 1 (2t * 1 ) ≥ D 1 (t * 1 ) + t * 1 D 1 (t * 1 ), hence -t * 1 D 1 (t * 1 ; n) ≥ D 1 (t * 1 ; n) -D 1 (2t * 1 ; n) (B.45)&(B.47) ≥ D1 (t * 1 ; n) -D1 (2t * 1 ; n) -1 n (B.46) = θ(t * 1 ) -θ(2t * 1 ) -1 n ≥ V (δ) -1 n .
For n ≥ N (δ)

def = max(2/V (δ), 2/(1 -δ)) we obtain -t * 1 D 1 (t * 1 ; n) ≥ V (δ)/2 def = γ(δ)
(δ) such that θ(t) - (t/2)θ (t) = δ is t * 1 (δ) = √ 2 • erfc -1 (δ).
Reasoning as for the case p = 2 we get that

lim n→∞ t * 1 (δ; n) = t * 1 (δ), lim n→∞ - t * 1 2 D 1 (t * 1 ; n) = - t * 1 (δ) 2 θ (t * 1 (δ)) > 0, lim n→∞ D 1 (t * 1 ; n) = θ(t * 1 (δ)), lim n→∞ α * 1 (δ; n) = θ(t * 1 (δ)) δ(δ -θ(t * 1 (δ))) . Since erfc(t * 1 / √ 2) = δ we have θ(t * 1 ) = δ - 2 π e - (t * 1 ) 2 2 t * 1 -δ(t * 1 ) 2 and thus (B.53) lim n→∞ α * 1 (δ; n) = δ -(δ -θ(t * 1 )) δ(δ -θ(t * 1 )) = 2 π e - (t * 1 ) 2 2 t * 1 -δ(t * 1 ) 2 -1 -1 δ . Lemma B.
= inf 0≤α≤A κ(α, β) is concave on [0, ∞). 2. The scalar t * = t * p (δ; n) (cf. Lemma B.4-Property 7) is well defined, with D p (t * ) < δ. 3. Define (B.54) α * = α * (δ; n) def = Dp(t * ) δ(δ-Dp(t * )) .
For A > α * and λ ≤ t * we have

(B.55) arg min α:0≤α≤A max β:0≤β≤1 κ(α, β) = α * .
The corresponding optimal β is β

* = β * (λ, δ; n) def = λ/t * . 4. For A > α * , λ ≤ t * , 0 < ≤ max(α * , A -α * ) we have (B.56) inf |α-α * |≥ κ(α)-κ(α * ) = inf |α-α * |= κ(α)-κ(α * ) ≥ ω( ) = ω p ( ; n, δ, λ) def = 2 2 λδ/t * (1+δ(α * + ) 2 ) 3/2 .
For the considered range of λ and , we have ω( ) ≤ 1/2.

p (λ/β) ≤ A 2 δ 2 1+δA 2 if and only if 0 < β ≤ β def = λ D -1 p (A 2 δ 2 /(1+δA 2 )) . Since A 2 δ 2 1+δA 2 < δ, this implies that for 0 < β ≤ β we can define (B.57) α(β) def = D p (λ/β) δ(δ -D p (λ/β))
.

A (β) > 0 if t = λ/β > t * (that is to say if β < β * def = λ/t * ); κ A (β) < 0 if β > β * ; and D p (t * ) < δ. A > α * implies D p (t * ) < A 2 δ 2 /(1 + δA 2 ), i.e., β * < β.
Combined with the fact that κ(0) = 0, this shows that the supremum of κ(β) over [0, β] is achieved uniquely at β * . This also implies that κ(β) is strictly decreasing for β * < β ≤ β. Being concave, κ A (β) must be also strictly decreasing for β ≥ β, so the supremum over [0, ∞) is indeed achieved at β * . Since λ ≤ t * we further have β * ≤ 1 hence this is also the supremum over β ∈ [0, 1]. To summarize, the optimal β is β * = λ/t * , and the corresponding optimal α is given as

(B.59) α * (β * ) = α(λ/t * ) = D p (t * ) δ(δ -D p (t * ))
.

4.

The assumption ≤ max(α * , Aα * ) ensures that the set {α : |α -α * | ≥ , 0 ≤ α ≤ A} is not empty. Since κ(α) is convex on [0, ∞) with its minimum at α * , we have

ω( ) def = inf α:|α-α * |≥ 0≤α≤A κ(α) -κ(α * ) = min α:|α-α * |= 0≤α≤A κ(α) -κ(α * ).
Since A > α * and λ ≤ t * , we have 0 < β * < 1. The second derivative of α → κ(α, β * ) with respect to α reads ∂ 2 κ(α,β * )

∂α 2 = β * δ (1+δα 2 ) 3/2 > 0. implying that on [0, A] ∩ [α * - , α * + ] the function α → κ(α, β * ) is strongly convex with strong convexity modulus β * δ (1+δ(α * + ) 2 ) 3/2 . Since α → κ(α, β * ) is minimum at α * , it holds that κ(α * ± , β * ) ≥ κ(α * , β * ) + 2 2 β * δ (1+δ(α * + ) 2 ) 3/2
. Furthermore, from the definition of κ(α) and β * , we have that κ(α) ≥ κ(α, β * ) for any α, with equality for α = α * . The claim therefore follows. Since λ ≤ t * and ≤ α * we have ω( ) ≤ δ(α * ) 2 2(1+δ(α * ) 2 ) 3/2 = f (1 + δ(α * ) 2 ) -1/2 with f (u) Invoking a lemma from [START_REF] Hjort | Asymptotics for Minimisers of Convex Processes[END_REF] we show that arg min α φ(α) concentrates around arg min α κ(α).

Lemma B.9 ([17, Lemma 2]). Let f (t) be a random convex function on some open set S ⊂ R p , and let t f be (one of ) its minimizer(s). Consider another function g(t) (which we interpret as approximating f ), such that it has a unique argmin t g . Then for each > 0, we have that: (g(s) -g(t g )) .

(B.
The role of f (t) and t f will be played by φ(α) and α * φ ; the role of g(t) and t g by κ(α) and α * . = [0, α * -] and S + = [α * + , A] its two convex components (at most one of them may be empty). Let φ S + (g, h) the value of (B.62), but with z 2 constrained to lie in S + (by convention, this is +∞ when S + = ∅). Similarly define φ S -(g, h). When S + is non-empty, since it is convex, we can effect the same simplifications and min-max swaps as in the proof of Lemma u Ax + λ x p -u e 1 .

We now want to show that for > 0 we have with high probability Φ > Φ = Φ 0 , because this is equivalent to where we additionally used that φ D 0 = φ P 0 since we optimize over convex sets (S 0 is a convex ball) and the penalty ψ(x, u) = λ x p -u e 1 is convex-concave (see, e.g., [START_REF] Sion | On General Minimax Theorems[END_REF]Corollary 3.3]).

z K = x K √ n ∈ S

  Fig.2.1. Frobenius norm of a random element of ginv 0 (A) for A a random Gaussian matrix of size 20 × 30 (left) and a sparse pseudoinverse spinv(A) (generically in ginv 0 (A); cf.[START_REF] Dokmanic | Beyond moore-penrose part II: the sparse pseudoinverse[END_REF]) of the same matrix (right). The random element of ginv 0 (A) is computed by selecting m columns of A at random and inverting the obtained submatrix. The plot shows results of 5 identical experiments, each consisting of generating a random 20 × 30 matrix and computing the two inverses 100 times. In the first experiment, the outlier norms extend to 2000 so they were clipped at 100. Green lines denote medians, and boxes denote the second and the third quartile.

7 Fig. 2 . 3 .

 723 Fig. 2.3. Comparison of the limiting (α * p ) 2 with the value of n m A † 2 F (left) and n m spinv(A) 2 F (right) for 10 realizations of A. Results are shown for δ ∈ {0.1, 0.2, 0.4, 0.7} and different values of n. Values for individual realizations are shown with colored dots with different color for every combination of n and δ. Horizontal dashed lines indicate the limiting value for the considered values of δ.

3. 3 .

 3 Making the bound (3.19) explicit. From now on we choose A def = 2α * and, for 0 < ≤ 1, we consider def = α * (which satisfies 0 < ≤ min(α * , Aα * ) = α * ). We use δ and

9 ,

 9 Lemma 2.1]. This work was supported in part by the European Research Council, PLEASE project (ERC-StG-2011-277906). Appendices. Appendix A. Results about Gaussian processes. A.1. Concentration of measure.

  Proofs and references. (a) [2, Corollary 2.3]; (b) (a) with a union bound; (c) X i = h 2 i is subexponential with parameters ν = 2, b = 4 [35, Example 2.4], i.e., E[e λ(Xi-µ) ] ≤ e ν 2 λ 2 2

  1). Combining the resulting bound with the bound on P{sup β∈[0,1] f h (β) > 2A } from (B.26) yields the result. Corollary B.3. Consider A > 0 and define for any set S ⊆ [0, A]: φ(α; g, h) With g ∼ N (0, I m ), h ∼ N (0, I n ), δ = (m -1)/n, we have for 0 < < 2 that (B.27) P sup S⊂[0,A] |φ S (g, h) -κ S | ≥ ≤ ζ(n, ). with ζ(n, ) = ζ(n, ; A, δ) defined in Lemma B.2. In particular, letting φ(α) def = φ(α; g, h), (B.28) P sup 0≤α≤A |φ(α) -κ(α)| ≥ ≤ ζ(n, ). Proof. To lighten notation we suppress the dependence of the stochastic function φ on random vectors g and h. By Lemma B.2 we have with probability at least 1 -ζ(n, ): for all 0 ≤ α ≤ A and 0 ≤ β ≤ 1, |φ(α, β) -κ(α, β)| ≤ . When this holds we have for any S ⊂ [0, A]:

  2 n . Combining all of the above yields (B.50). • Step 9. (Proof of Lemma B.7). By (B.36) and (B.37) we have for any n ≥ 2/(1 -δ)

8 ( 1 .

 81 Deterministic properties of κ). Let m, n, 1 ≤ m < n be two integers, δ def = (m -1)/n, 1 ≤ p ≤ ∞, κ(α, β) defined in (B.23), D p (t) defined in (B.31). The following hold: The function κ(α, β) is convex-concave and proper on [0, ∞) × [0, ∞), hence the function κ(α) def = sup 0≤β≤1 κ(α, β) is convex on [0, ∞), and for any A > 0 the function κ A (β) def

2 .

 2 We have δ def = (m -1)/n < 1, and by Lemma B.4, Property 4, D p (0) ≥ n n+1 . Because we consider the underdetermined case, 1 ≤ m < n, we have n ≥ 2 and δ ≤ (n -2)/n ≤ n/(n + 1) ≤ D p (0).

3 .

 3 Since κ(α, β) is convex-concave and proper, and the constraint sets in (B.55) convex and compact, we can change the order of maximization and minimization [28, Corollary 3.3]. (Minimization over α) For β = 0 and any λ ≥ 0 we have ∆ p (β, λ) = 0 hence κ A (0) = inf 0≤α≤A κ(α, 0) = 0. For β > 0, observing that ∆ p (β, λ) = β D p (λ/β) we rewrite κ(α, β) = β( δα 2 + 1 -α D p (λ/β)). With D -1 p (y) def = inf {t : D p (t) ≤ y} and D p strictly decreasing, we have D

  and check that α(β) ≤ A. By studying the sign of ∂κ(α,β)∂α = β δα √ δα 2 +1 -D p (λ/β) , we get that α → κ(α, β) has a unique minimizer on [0, A] which is precisely α * (β) = α(β).It follows that for 0 < β ≤ β we have:(B.58) κ A (β) = min 0≤α≤A κ(α, β) = κ(α * (β), β) = β δ -D p (λ/β) δ .(Maximization over β) The sign of κ A (β) is that of δg(λ/β) with g(t) def = D p (t) -

t 2 D

 2 p (t) as in Lemma B.4-Property 7. Hence, we have: κ

def = 1 2 ( 1 /u 2 - 1 )u 3 = u-u 3 2 ≤ 1 /

 2121321 2 for 0 < u ≤ 1. Hence, ω( ) ≤ 1/2.

2 , 2 ≤ 2 ≤: u 2 =β 1 √ n z 2 g u - 1 √ n u 2

 222112 Lemma B.10. Let A > α * , λ ≤ t * , with α * defined as in Lemma B.8-Equation (B.55) and t * = t * p (δ; n) as in Lemma B.4-Property 7. Consider the random function φ(α) defined as in Corollary B.3, and α * φ def = arg min 0≤α≤A φ(α). For 0 < ≤ max(α * , Aα * ) we have (B.61) P α * φ -α * ≥ ≤ ζ n, ω( ) with ζ(n, ) = ζ(n, ; A, δ) defined in Lemma B.2 and ω( ) defined in (B.56). Proof. Since 0 < ≤ max(α * , Aα * ) the set {α : 0 ≤ α ≤ A, |α -α * | ≤ } is a non-empty subset of [0, A], and sup α:0≤α≤A, |α-α * |≤ |φ(α) -κ(α)| ≤ sup 0≤α≤A |φ(α) -κ(α)| . Since φ is a random convex function, we can apply Lemma B.9 to obtain P α * φ -α * ≥ ≤ P sup α:0≤α≤A, |α-α * |≤ |φ(α) -κ(α)| ≥ ω( ) P sup 0≤α≤A |φ(α) -κ(α)| ≥ ω( ) ζ(n, ω( )/2), where we used that ω( ) ≤ inf α:0≤α≤A, |α-α * |= κ(α) -κ(α * ), and the last inequality follows from Corollary B.3 which we can use since ω( )/2 ≤ 1/4 < 2. Lemma B.11. Let A > α * , λ ≤ t * with α * defined as in Lemma B.8-Equation (B.55) and t * = t * p (δ; n) as in Lemma B.4-Property 7. For 0 ≤ ≤ max(α * , Aα * ), consider the optimal cost of the auxiliary optimization (3.14) with an altered order of minimization and maximization and z 2 further restricted to be at least at distance from α * (B.62) φ (g, h) def = max β:0≤β≤1 w: w p * ≤1 min z: z 2 ≤A z 2 / ∈(α * -,α * + ) max uh zu e 1 + λ √ n w z. With g ∼ N (0, I m ), h ∼ N (0, I n ), 1 ≤ m < n, δ = (m -1)/n we have for any 0 < η < 2: (B.63) φ 0 (g, h) < κ(α * ) + η and φ (g, h) > κ(α * ) + ω( ) -η, with probability at least 1-ζ(n, η), where ζ(n, ) = ζ(n, ; A, δ) from Lemma B.2, ω( ) from (B.56). Proof. Since 0 < ≤ max(α * , Aα * ) the set S def = {α : 0 ≤ α ≤ A, |α -α * | ≤ } is a nonempty subset of [0, A]. Denote S -def

2 .| √ n x 2

 22 3.1 (from (3.15) to (3.16)) to arrive at φ S + (g, h) = min α:α * + ≤α≤A max β:0≤β≤1 φ(α, β; g, h), and similary with S -we get when it is non-empty that φ S -(g, h) = min α:0≤α≤α * -max β:0≤β≤1 φ(α, β; g, h). This shows that φ (g, h) = min(φ S -(g, h), φ S + (g, h)) = φ S (g, h) where the notation φ S (g, h) matches that used in Corollary B.3. Moreover by definition (see Lemma B.8) we have κ S def = min α∈S max 0≤β≤1 κ(α, β) ≥ κ(α * ) + ω( ). By Corollary B.3 we have, for 0 < η < 2, with probability at least 1 -ζ(n, η): for all S ⊂ [0, A], |φ S (g, h) -κ S | < η. Specializing to S = [0, A] and S = S and combining the above yieldsφ 0 (g, h) = φ [0,A] (g, h) < κ [0,A] + η = κ(α * ) + η, φ (g, h) = φ S (g, h) > κ S -η ≥ κ(α * ) + ω( ) -η. Lemma B.12. Let K > α * / √ n, λ ≤ t * with α * definedas in Lemma B.8-Equation (B.55) and t * = t * p (δ; n) as in Lemma B.4-Property 7. Denote by x K any optimal solution of (3.11). For 0 < ≤ max(α * , K √ nα * ) we have P x K -α * √ n ≥ √ n ≤ 4ζ n, ω( ) with ζ(n, ) = ζ(n, ; K √ n, δ) defined in Lemma B.2 and ω( ) defined in (B.56). Proof. Denote Φ the optimal cost of (3.11) and Φ the corresponding cost when z = x √ n is further restricted to S def = {z : z 2 ≤ A and | z 2 -α | ≥ }, with A def -α * |≥ max u: u 2 ≤1

def = {z : z 2 ≤

 2 A and | z 2 -α * | < }. By Theorem A.3 (i) and (ii), denoting φ P (resp. φ D ) the optimum value of the "primal" (resp. "dual") auxiliary optimization problem associated to (B.64), we have for any c ∈ R (B.65) P{Φ < c} ≤ 2P{φ P ≤ c} and P{Φ 0 > c} ≤ 2P{φ D 0 ≥ c},

2

  F . This is a consequence of the technique used to bound inf |α-α * |≥ κ(α) -κ(α * ) in Lemma B.8 which relies on strong convexity of κ. Whether a more refined analysis could lead to better error bars remains an open question.

	Corollaries 2.3 and 2.4 prove that A † 2 F and spinv(A)

Table 2 . 1

 21 Ratio of squared Frobenius norms.

	δ	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
	Tomo 3.56 2.73 2.26 1.98 1.74 1.55 1.45 1.32
	Gauss 2.59 2.01 1.69 1.49 1.34 1.22 1.13 1.06

  Axe 1 2 + λ x p . (3.9) By Lemma B.1, since the p norm is L-Lipschitz with respect to the 2 norm (with

			4 ,
	which is exactly the statement of Theorem 2.2.
	3.1. Proof of the Main Vector Result, Lemma 3.1. Define
	(3.8)	x * = arg min Ax=e1	x p ,
		x = arg min

x

  (d) [START_REF] Ledoux | Concentration of Measure and Logarithmic Sobolev Inequalities[END_REF] Eq. (1.22)]; (e) union bound applied to (d); (f) a consequence of Poincaré inequality for Gaussian measures[START_REF] Ledoux | Concentration of Measure and Logarithmic Sobolev Inequalities[END_REF] Eq. (2.16)]:

			> n.
	P	h	2 2 -n ≥	1 b , and µ = E[X i ] = 1. Applying [35, Proposition 2.2] then yields √ n ≤ 2e -8 , for 0 ≤ ≤ n, and P h 2 2 -n ≥ √ n ≤ 2e -√ n 8 , for

  that is, 2 -lasso gives the same optimizer as equality-constrained minimization.

	Proof. Using [33, Corollary 5.35] 12 , we have for any ≥ 0
	(B.21)	P[σ min

  and define C t = C t,p : x p * ≤ t and D p (t; n) as in (B.31). Using D p (t) as a shorthand, the following hold: 1. The sets C t are convex and nested with C t C t for t < t ; 2. For any vector h, the function t → dist(h, C t ) is non-increasing and convex; We recall that x → dist(x, C) is convex for convex C [3, Example 3.16]. Next, (x, t) → tdist(x/t, C) is convex in both arguments because it is the perspective of x → dist(x, C) [3, Chapter 2]. Applying this to C = C 1 and observing that dist(h, C t ) = tdist(h/t, C 1 ) we obtain that dist(h, C t ) is convex in t. The fact that it is non-increasing follows from Property 1. 3. Since expectation of convex functions is convex, and the square of a non-negative convex function is convex, D p (t) is convex as claimed. That it is (strictly) decreasing is obvious. 4. For any y ∈ R n and p ≥ 1, y p

	3. D p (t) is a (strictly) decreasing convex function of t;
	4. lim t→∞ D p (t) = 0; 5. n n+1 ≤ D p (0) ≤ 1; 6. The function t → D p (t) is infinitely differentiable;
	7. Let g(t) = g(t; n)	def = D p (t) -t 2 D p (t). For any 0 < δ < D p (0) there is a unique
		t * = t * p (δ; n) ∈ (0, ∞)
	such that g(t) > δ for t < t Proof. 1. Obvious. 2.

def = x ∈ R n * and g(t) < δ for t > t * . It holds that D p (t * ) < g(t * ) = δ. * ≤ y 1 ≤

√ n y 2 . Hence, for any given t > 0, dist(y, C t ) = 0 as soon as y 2 ≤ t/ √ n and we can write for all p ≥ 1 that

  p ), which yields (B.41).• Step 2. We establish that for any p, n, δ, with the shorthand t *

		p = t * p (δ; n),
	(B.42)	D p (t * p /2; n) ≥ δ,
	(B.43)	D p (t * p ; n) ≤ δ.
	With another shorthand D p (t)

def = D p (t; n) and the convexity of D p (t), we have for all t, h (B.44) D p (t + h) ≥ D p (t) + hD p (t). Applying it to t = t * p and h = -t * p /2 and using the definition of t * p , we get D p (t * p /2) ≥ D p (t * p ) -(t * p /2)D p (t * p ) = δ, i.e., (B.42) holds. Since D p (t) is non-increasing, we have D p (t) ≤ 0 and D p (t) -t 2 D p (t) ≥ D p (t) for any t. Applying to t = t * p this establishes (B.43) by definition of t * p . • Step 3. Let Dp (t; n

  > 0 which establishes (B.7). By (B.45)-(B.46)-(B.47) we have θ(t) -1/n ≤ D 1 (t; n) ≤ θ(t) for all t and n. Hence, the sequence of convex differentiable functions {D 1 ( • ; n)} n converges uniformly to the convex and smooth function θ(t) which implies convergence of the derivatives, lim n→∞ D 1 (t; n) = θ (t). As for p = 2, this shows lim n→∞ {D 1 (t; n) -(t/2)D 1 (t; n)} = θ(t) -(t/2)θ (t).

	By Lemma A.2, θ(t) -(t/2)θ (t) = erfc(t/	√	2) so the unique t = t * 1

  Proof of Lemma B.8. 1. It is obvious that κ is proper. Convexity in α is easy to check by computing the second derivative. Concavity in β follows from the convexity of β → ∆ p (β; h, λ) which is a distance to a convex set [3, Example 3.16], and the fact that the expectation ∆ p (β, λ) of a convex function is convex. As a result, κ(α) is convex and κ(β) is concave.

  60) P{ t f -t g 2 ≥ } ≤ P sup

s-tg 2 ≤ |f (s) -g(s)| ≥ 1 2 inf s-tg 2 =

We only study real matrices.

For p = 1, ginv p (A) is a singleton except for a set of matrices of measure zero; a precise statement is given in Section 2.

A careful reader will notice that the assumptions of Theorem 2.1 forbid many types of sparse matrices. Indeed, it is known that sparse frames can have sparser duals than generic frames[START_REF] Krahmer | Sparsity and Spectral Properties of Dual Frames[END_REF][START_REF] Li | Sparse Dual Frames and Dual Gabor Functions of Minimal Time and Frequency Supports[END_REF].

The existence of γ(δ) and N (δ) will be proved below for p ∈ {1, 2}.

The results in[START_REF] Halko | Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[END_REF] are designed for the nonasymptotic regime where the matrix is essentially square.

For reproducible research, code is available online at https://github.com/doksa/altginv.

We remark that universality of Gaussians is a general phenomenon that goes beyond examples in[START_REF] Donoho | Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing[END_REF][START_REF] Oymak | Universality laws for randomized dimension reduction, with applications, Information and Inference[END_REF].

With respect to the Lebesgue measure.

-(α * ) 2 ≥ m (α * ) 2 = ( * ).

An analogous result does not hold for the squared lasso (except for λ = 0 + ).

Convex in the first argument, concave in the second one.

The CGMT contains a similar statement, albeit we need a different derivation to get exponential concentration.

We actually use a one-sided variant of[START_REF] Vershynin | Introduction to the non-asymptotic analysis of random matrices[END_REF] Corollary 5.35] which can be obtained by combining Lemma A.1(d) with the estimate of the expectation of σ min ,[START_REF] Vershynin | Introduction to the non-asymptotic analysis of random matrices[END_REF] Theorem 5.32].

Let C(z, u, w) = C(z, u, z; g, h) be the objective function in (3.14) Denote by x K any optimal solution of the random bounded problem (3.11) and x any optimal solution of the random unbounded problem (3.9). For 0 < ≤ min(α * , K √ nα * ) we have Proof. To handle non-uniqueness, x (resp. x K ) may denote the convex set of solutions of the respective convex optimization problems. The property x = x K then means that the sets do not intersect, and inequalities such as f ( x) > c are meant to hold for all elements of the set x.

We first prove, by contradiction, that if x = x K , then necessarily x K 2 = K. Suppose that the opposite holds: x = x K , but x K 2 < K. Since x = x K we have x 2 > K. Denoting the objective in (3.9) by φ(x), this means that φ( x) < φ( x K ). By convexity of φ it follows that all points on the line segment

We conclude using Lemma B.12.

Lemma B.14. With ∆ p defined as in the statement of Lemma B.2, the function

Proof. We omit the dependency in λ for brevity and write by definition