is more robustly recovered than its coefficients $\bm{z}_{\ell^{\smash{1}}}$,
or vice versa. This can be seen by comparing coefficient and signal recovery
in the Subfigures 8(a)-8(d).333Note that the quantity
$\lambda_{\text{min}}\left(\bm{D}_{\texttt{super}};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{4})\right)$
is very small. Hence, even for a small amount of noise the error of Equation
(3.4) explodes. For $\eta>0.1$ the error stays roughly constant since the
solution $\hat{\bm{z}}$ of ($\text{BP}_{\eta}^{\text{\smash{coef}}}$) is
always close to $\bm{0}$. If
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)\ll
1$, coefficient recovery is less robust than signal recovery, see Subfigures
8(a), 8(b) and 8(d). However, if
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)\gg
1$, the contrary holds true, see Subfigure 8(c).

(a)

(b)

(c)

(d)

(e)

(f)

Figure 8: Robustness to measurement noise. We display the reconstruction
errors for a recovery from noisy measurements with an increasing noise level.
The first four Subfigures are based on the examples for coefficient recovery
of Section 5.1, and the the last two on the examples based on Haar wavelet of
Section 5.2. We use the notation
$\mathcal{D}=\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}}^{i})$,
where $\bm{z}_{\ell^{\smash{1}}}^{\smash{i}}\in Z_{\ell^{\smash{1}}}$.

## Acknowledgments

Acknowledgements: M.M. is supported by the DFG Priority Programme DFG-SPP
1798. He wishes to thank Martin Genzel for inspiring discussions. C.B. have
been supported by a PEPS « Jeunes chercheuses et jeunes chercheurs » funding
in 2017 and 2018 for this work. P.W. and J.K. are supported by the ANR JCJC
OMS.

## References

  * [ALMT14] Dennis Amelunxen, Martin Lotz, Michael B. McCoy and Joel A. Tropp  “Living on the edge: phase transitions in convex programs with random data”  In _Inf. Inference_ 3.3, 2014, pp. 224–294
  * [ALW20] D. Amelunxen, M. Lotz and J. Walvin  “Effective condition number bounds for convex regularization” in press  In _IEEE Trans. Inf. Theory_ , 2020
  * [B+17] Richard Baraniuk, Hyeokho Choi and Ramesh Neelamani  “Rice Wavelet Toolbox, Version 3”, URL: https://github.com/ricedsp/rwt, 2017
  * [BEL13] H. Bristow, A. Eriksson and S. Lucey  “Fast Convolutional Sparse Coding”  In _2013 IEEE Conference on Computer Vision and Pattern Recognition_ , 2013
  * [Beu38] A. Beurling  “Sur les intégrales de Fourier absolument convergentes et leur application à une transformation fonctionnelle”  In _Ninth Scandinavian Mathematical Congress_ , 1938, pp. 345–366
  * [BF13] Ewout Berg and Michael P. Friedlander  “Spot – A Linear-Operator Toolbox”, URL: http://www.cs.ubc.ca/labs/scl/spot/index.html, 2013
  * [BM02] Peter L. Bartlett and Shahar Mendelson  “Rademacher and Gaussian complexities: Risk bounds and structural results”  In _J. Mach. Learn. Res._ 3, 2002, pp. 463–482
  * [CCL19] Peter G. Casazza, Xuemei Chen and Richard G. Lynch  “Preserving Injectivity under Subgaussian Mappings and Its Application to Compressed Sensing” arXiv preprint: 1710.09972, 2019
  * [CDS98] S. Chen, D. Donoho and M. Saunders  “Atomic Decomposition by Basis Pursuit”  In _SIAM J. Sci. Comput._ 20.1, 1998, pp. 33–61
  * [CENR11] Emmanuel J. Candès, Yonina C. Eldar, Deanna Needell and Paige Randall  “Compressed sensing with coherent and redundant dictionaries”  In _Appl. Comput. Harmon. Anal._ 31.1, 2011, pp. 59–73
  * [CF14] Emmanuel J. Candès and Carlos Fernandez-Granda  “Towards a Mathematical Theory of Super-resolution”  In _Commun. Pur. Appl. Math._ 67.6, 2014, pp. 906–956
  * [CK13] “Finite Frames: Theory and Applications”, Applied and Numerical Harmonic Analysis  Birkhäuser, 2013
  * [CM73] J.. Claerbout and F. Muir  “Robust Modeling With Erratic Data”  In _Geophysics_ 38.5, 1973, pp. 826–844
  * [CR06] Emmanuel J Candès and Justin Romberg  “Quantitative robust uncertainty principles and optimally sparse decompositions”  In _Found. Comput. Math._ 6.2 Springer, 2006, pp. 227–254
  * [CRPW12] Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo and Alan S. Willsky  “The convex geometry of linear inverse problems”  In _Found. Comput. Math._ 12.6, 2012, pp. 805–849
  * [CRT06] E.. Candès, J. Romberg and T. Tao  “Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information”  In _IEEE Trans. Inf. Theor._ 52.2, 2006, pp. 489–509
  * [CRT06a] Emmanuel J. Candès, Justin K. Romberg and Terence Tao  “Stable signal recovery from incomplete and inaccurate measurements”  In _Comm. Pure Appl. Math._ 59.8, 2006, pp. 1207–1223
  * [CT06] E.. Candès and T. Tao  “Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?”  In _IEEE Trans. Inf. Theor._ 52.12, 2006, pp. 5406–5425
  * [CWW14] Xuemei Chen, Haichao Wang and Rongrong Wang  “A null space analysis of the $\ell_{1}$-synthesis method in dictionary-based compressed sensing”  In _Appl. Comput. Harmon. Anal._ 37.3, 2014, pp. 492–515
  * [CX15] Jian-Feng Cai and Weiyu Xu  “Guarantees of total variation minimization for signal recovery”  In _Inf. Inference_ 4.4, 2015, pp. 328–353
  * [DE03] D.. Donoho and M. Elad  “Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^{1}$ minimization”  In _Proc. Natl. Acad. Sci._ 100.5, 2003, pp. 2197–2202
  * [DH01] D.. Donoho and X. Huo  “Uncertainty principles and ideal atomic decomposition”  In _IEEE Trans. Inf. Theory_ 47.7, 2001, pp. 2845–2862
  * [DHL17] Arnak S. Dalalyan, Mohamed Hebiri and Johannes Lederer  “On the prediction performance of the Lasso”  In _Bernoulli_ 23.1, 2017, pp. 552–581
  * [DNW13] M.. Davenport, D. Needell and M.. Wakin  “Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries”  In _IEEE Trans. Inf. Theory_ 59.10, 2013, pp. 6820–6829
  * [Don06] David L. Donoho  “Compressed sensing”  In _IEEE Trans. Inf. Theory_ 52.4, 2006, pp. 1289–1306
  * [EB02] Michael Elad and Alfred M Bruckstein  “A Generalized Uncertainty Principle and Sparse Representation in Pairs of Bases”  In _IEEE Trans. Inf. Theory_ 48.9 Citeseer, 2002
  * [EMR07] M. Elad, P. Milanfar and R. Rubinstein  “Analysis versus synthesis in signal priors”  In _Inverse Probl._ 23.3, 2007, pp. 947–968
  * [FR13] Simon Foucart and Holger Rauhut  “A Mathematical Introduction to Compressive Sensing”, Applied and Numerical Harmonic Analysis  Birkhäuser, 2013
  * [Fuc04] J.-J. Fuchs  “On sparse representations in arbitrary redundant bases”  In _IEEE Trans. Inf. Theory_ 50.6, 2004, pp. 1341–1344
  * [Fuc05] Jean-Jacques Fuchs  “Recovery of exact sparse representations in the presence of bounded noise”  In _IEEE Trans. Inf. Theory_ 51.10 IEEE, 2005, pp. 3601–3608
  * [FV99] Robert M. Freund and Jorge R. Vera  “Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm”  In _SIAM J. Optim._ 10.1, 1999, pp. 155–176
  * [GB08] Michael Grant and Stephen Boyd  “Graph implementations for nonsmooth convex programs”  In _Recent Advances in Learning and Control_ 371, Lecture Notes in Control and Information Sciences  Springer London, 2008, pp. 95–110
  * [GB14] Michael Grant and Stephen Boyd  “CVX: Matlab Software for Disciplined Convex Programming, version 2.1”, URL: http://cvxr.com/cvx, 2014
  * [GKM20] M. Genzel, G. Kutyniok and M. März  “$\ell^{1}$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?” Accepted, arXiv preprint: 1710.04952  In _Appl. Comput. Harmon. Anal._ , 2020
  * [GLCS20] Adityanand Guntuboyina, Donovan Lieu, Sabyasachi Chatterjee and Bodhisattva Sen  “Adaptive risk bounds in univariate total variation denoising and trend filtering”  In _Ann. Statist._ 48.1, 2020, pp. 205–229
  * [GM04] A.. Giannopoulos and V.. Milman  “Asymptotic Convex Geometry Short Overview”  In _Different Faces of Geometry_ Springer, 2004, pp. 87–162
  * [GMS20] M. Genzel, M. März and R. Seidel  “Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery” arXiv preprint: 2001.09952, (2020)  arXiv:2001.09952
  * [GN03] R. Gribonval and M. Nielsen  “Sparse representations in unions of bases”  In _IEEE Trans. Inf. Theory_ 49.12, 2003, pp. 3320–3325
  * [GNEGD14] R. Giryes, S. Nam, M. Elad, R. Gribonval and M.. Davies  “Greedy-like algorithms for the cosparse analysis model”  In _Linear Algebra Appl._ 441, 2014, pp. 22–60
  * [Gor85] Yehoram Gordon  “Some inequalities for Gaussian processes and applications”  In _Isr. J. Math._ 50.4, 1985, pp. 265–289
  * [Gor88] Yehoram Gordon  “On Milman’s inequality and random subspaces which escape through a mesh in $\mathbb{R}^{n}$”  In _Geometric aspects of functional analysis_ 1317, Lecture Notes in Mathematics  Springer, 1988, pp. 84–106
  * [HS10] R Henrion and A. Seeger  “On Properties of Different Notions of Centers for Convex Cones”  In _Set-Valued Anal._ 18, 2010, pp. 205–231
  * [HS10a] René Henrion and Alberto Seeger  “Inradius and Circumradius of Various Convex Cones Arising in Applications”  In _Set-Valued Anal._ 18, 2010, pp. 483–511
  * [HS10b] J-B Hiriart-Urruty and Alberto Seeger  “A variational approach to copositive matrices”  In _SIAM Rev._ 52.4, 2010, pp. 593–629
  * [IS08] A. Iusem and A. Seeger  “Normality and modulability indices. Part I: Convex cones in normed spaces”  In _J. Math. Anal. Appl._ 338.1, 2008, pp. 365–391
  * [KNW15] Felix Krahmer, Deanna Needell and Rachel Ward  “Compressive Sensing with Redundant Dictionaries and Structured Measurements”  In _SIAM J. Math. Anal._ 47.6, 2015, pp. 4606–4629
  * [KR15] Maryia Kabanava and Holger Rauhut  “Analysis $\ell_{1}$-recovery with Frames and Gaussian Measurements”  In _Acta Appl. Math._ 140.1, 2015, pp. 173–195
  * [Kre38] M.G. Kreǐn  “The L-problem in an abstract normed linear space” English Transl. Amer. Math. Soc., Providence, R.I., 1962. MR 29 # 5073  In _Some questions in the theory of moments_ Gos. Naučno-Tehn. Izdat. Ukraine, 1938
  * [KRZ15] M. Kabanva, H. Rauhut and H. Zhang  “Robust analysis $\ell_{1}$-recovery from Gaussian measurements and total variation minimization”  In _Eur. J. Appl. Math._ 26.6, 2015, pp. 917–929
  * [LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio and Patrick Haffner  “Gradient-based learning applied to document recognition”  In _Proc. IEEE_ 86.11, 1998, pp. 2278–2324
  * [LJ11] Max A. Little and Nick S. Jones  “Generalized methods and solvers for noise removal from piecewise constant signals. I. Background theory”  In _Proc. Royal Soc. Lond. A_ 467.2135, 2011, pp. 3088–3114
  * [LLMLY12] Y. Liu, S. Li, T. Mi, H. Lei and W. Yu  “Performance analysis of $\ell_{1}$-synthesis with coherent frames”  In _2012 IEEE International Symposium on Information Theory Proceedings_ , 2012, pp. 2042–2046
  * [LMPV17] Christopher Liaw, Abbas Mehrabian, Yaniv Plan and Roman Vershynin  “A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets”  In _Geometric Aspects of Functional Analysis_ 2169, Lecture Notes in Mathematics  Springer, 2017, pp. 277–299
  * [Log65] B. Logan  “Properties of High-Pass Signals”, 1965
  * [Mal09] S. Mallat  “Cover image A Wavelet Tour of Signal Processing: The Sparse Way”  Elsevier, 2009
  * [Mil85] V.. Milman  “Random subspaces of proportional dimension of finite dimensional normed spaces: Approach through the isoperimetric inequality”  In _Banach Spaces_ 1166, Lecture Notes in Mathematics  Springer Berlin Heidelberg, 1985, pp. 106–115
  * [MK87] Katta G Murty and Santosh N Kabadi  “Some NP-complete problems in quadratic and nonlinear programming”  In _Math. Program._ 39.2 Springer, 1987, pp. 117–129
  * [MPT07] Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann  “Reconstruction and subgaussian operators in asymptotic geometric analysis”  In _Geom. Funct. Anal._ 17.4, 2007, pp. 1248–1282
  * [MZ93] S.. Mallat and Zhifeng Zhang  “Matching pursuits with time-frequency dictionaries”  In _IEEE Trans. Signal Process._ 41.12, 1993, pp. 3397–3415
  * [NDEG13] S. Nam, M.. Davies, M. Elad and R. Gribonval  “The cosparse analysis model and algorithms”  In _Appl. Comput. Harmon. Anal._ 34.1, 2013, pp. 30–56
  * [PRK93] Y.. Pati, R. Rezaiifar and P.. Krishnaprasad  “Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition”  In _Proceedings of 27th Asilomar Conference on Signals, Systems and Computers_ , 1993, pp. 40–44 vol.1
  * [Ren95] J. Renegar  “Linear programming, complexity theory and elementary functional analysis”  In _Math. Program._ 70, 1995, pp. 279–351
  * [Roc70] Ralph Tyrell Rockafellar  “Convex Analysis”  Princeton University Press, 1970
  * [ROF92] L. Rudin, S. Osher and E. Fatemi  “Nonlinear total variation based noise removal algorithms”  In _Physica D_ 60.1–4, 1992, pp. 259–268
  * [RSV08] H. Rauhut, K. Schnass and P. Vandergheynst  “Compressed Sensing and Redundant Dictionaries”  In _IEEE Trans. Inf. Theory_ 54.5, 2008, pp. 2210–2219
  * [RV07] M. Rudelson and R. Vershynin  In _Comm. Pure Appl. Math._ 61.8, 2007, pp. 1025–1045
  * [SF09] Ivan W. Selesnick and Mário A.. Figueiredo  “Signal restoration with overcomplete wavelet transforms: comparison of analysis and synthesis priors”  In _Proceedings of SPIE, Wavelets XIII_ 7446, 2009
  * [ST03] Alberto Seeger and Mounir Torki  “On eigenvalues induced by a cone constraint”  In _Linear Algebra Appl._ 372 Elsevier, 2003, pp. 181–206
  * [Sto09] Mihailo Stojnic  “Various thresholds for $\ell_{1}$-optimization in compressed sensing” Preprint arXiv:0907.3666, 2009
  * [Syl57] James Joseph Sylvester  “A question in the geometry of situation”  In _Quarterly Journal of Pure and Applied Mathematics_ 1.1, 1857, pp. 79–80
  * [Tal14] Michel Talagrand  “Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems”  Springer, 2014
  * [TBM79] H.. Taylor, S.. Banks and J.. McCoy  “Deconvolution with the $\ell 1$ norm”  In _Geophysics_ 44.1, 1979, pp. 39–52
  * [Tro04] J.. Tropp  “Greed is good: algorithmic results for sparse approximation”  In _IEEE Trans. Inf. Theory_ 50.10, 2004, pp. 2231–2242
  * [Tro06] Joel A Tropp  “Just relax: Convex programming methods for identifying sparse signals in noise”  In _IEEE Trans. Inf. Theory_ 52.3, 2006, pp. 1030–1051
  * [Tro15] Joel A. Tropp  “Convex Recovery of a Structured Signal from Independent Random Linear Measurements”  In _Sampling Theory, a Renaissance_ , Applied and Numerical Harmonic Analysis  Birkhäuser, 2015, pp. 67–101
  * [Ver12] Roman Vershynin  “Introduction to the non-asymptotic analysis of random matrices”  In _Compressed Sensing Theory and Applications_ Cambridge University Press, 2012, pp. 210–268
  * [Ver15] Roman Vershynin  “Estimation in High Dimensions: A Geometric Perspective”  In _Sampling Theory, a Renaissance: Compressive Sensing and Other Developments_ Cham: Springer International Publishing, 2015, pp. 3–66
  * [Ver18] Roman Vershynin  “High-Dimensional Probability: An Introduction with Applications in Data Science”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2018
  * [Woh14] B. Wohlberg  “Efficient convolutional sparse coding”  In _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014, pp. 7173–7177
  * [Zuh48] S.I. Zuhovickiĭ  “Remarks on problems in approximation theory” (Ukrainian)  In _Mat. Zbirnik KDU_ , 1948, pp. 169–183

##  Appendix A Proofs of Section 3

###  A.1 Proof of Lemma 3.2 (Minimal $\ell^{1}$-Representers)

  1. (b)

“$\Rightarrow$”: Assume that $\hat{X}=\left\\{\bm{x}_{0}\right\\}$. First, we
show that $Z_{\ell^{\smash{1}}}\subseteq\hat{Z}$: Let
$\bm{z}_{\ell^{\smash{1}}}\in Z_{\ell^{\smash{1}}}$. Since
$\bm{D}\bm{z}_{\ell^{\smash{1}}}=\bm{x}_{0}$, $\bm{z}_{\ell^{\smash{1}}}$ is
in the feasible set of ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$).
Furthermore, due to $\hat{X}=\left\\{\bm{x}_{0}\right\\}$ it holds true that
$\bm{D}\hat{\bm{z}}=\bm{x}_{0}$ for each $\hat{\bm{z}}\in\hat{Z}$. Thus also
$\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}\leq\left\|\hat{\bm{z}}\right\|_{1}$
and therefore $\bm{z}_{\ell^{\smash{1}}}\in\hat{Z}$. Secondly, we show
$\hat{Z}\subseteq Z_{\ell^{\smash{1}}}$. For a $\hat{\bm{z}}\in\hat{Z}$ it
holds true that $D\hat{\bm{z}}=\bm{x}_{0}$ since we have assumed that
$\hat{X}=\left\\{\bm{x}_{0}\right\\}$. Thus, $\hat{\bm{z}}$ is also feasible
for $Z_{\ell^{\smash{1}}}$. Since each $\bm{z}_{\ell^{\smash{1}}}\in
Z_{\ell^{\smash{1}}}$ is in turn feasible for $\hat{Z}$, we obtain that
$\left\|\hat{\bm{z}}\right\|_{1}\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}$
and therefore $\hat{\bm{z}}\in Z_{\ell^{\smash{1}}}$.
“$\Leftarrow$”: If $\hat{Z}=Z_{\ell^{\smash{1}}}$, then
$\hat{X}=\bm{D}\cdot\hat{Z}=\bm{D}\cdot
Z_{\ell^{\smash{1}}}=\left\\{\bm{x}_{0}\right\\}$.

  2. (a)

If $\hat{Z}=\left\\{\bm{z}_{0}\right\\}$, then also
$\hat{X}=\bm{D}\cdot\hat{Z}=\left\\{\bm{x}_{0}\right\\}$ and (b) would imply
$Z_{\ell^{\smash{1}}}=\hat{Z}=\left\\{\bm{z}_{0}\right\\}$.

###  A.2 Proof of Lemma 3.4 (The Gauge Formulation)

By definition,

$\displaystyle\hat{X}$
$\displaystyle=\bm{D}\cdot\left(\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{
s.t }\quad{\left\|\bm{y}-\bm{A}\bm{D}\bm{z}\right\|_{2}\leq\eta}\right)$ (A.1)
$\displaystyle=\bm{D}\cdot\left(\operatorname*{argmin}_{\bm{z}\in\mathbb{R}^{d}}\inf\left\\{\lambda>0:\bm{z}\in\lambda\cdot\text{B}_{1}^{\smash{d}}\right\\}\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{D}\bm{z}\right\|_{2}\leq\eta\right)$ (A.2)
$\displaystyle=\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{n}}\inf\left\\{\lambda>0:\bm{x}\in\lambda\cdot\bm{D}\cdot\text{B}_{1}^{\smash{d}}\right\\}\quad\mbox{
s.t. }\quad\left\|\bm{y}-\bm{A}\bm{x}\right\|_{2}\leq\eta.$ (A.3)

###  A.3 Proof of Lemma 3.5 (Descent Cone of the Gauge)

We will only prove the first equality and note that the other one follows
essentially the same argumentation. Pick any $\bm{z}_{\ell^{\smash{1}}}\in
Z_{\ell^{\smash{1}}}$ and note that
$p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{x}_{0})=\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}$.
“$\supseteq$”: Let
$\bm{h}\in\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})$,
i.e., there exists a $\tau>0$ such that
$\left\|\bm{z}_{\ell^{\smash{1}}}+\tau\bm{h}\right\|_{1}\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}$.
Hence,

$p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{D}\bm{z}_{\ell^{\smash{1}}}+\tau\bm{D}\bm{h})=p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{D}\cdot(\bm{z}_{\ell^{\smash{1}}}+\tau\bm{h}))\leq\left\|\bm{z}_{\ell^{\smash{1}}}+\tau\cdot\bm{h}\right\|_{1}\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}=p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{x}_{0}),$

and therefore
$\bm{D}\bm{h}\in\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$.
“$\subseteq$”: Let
$\bm{x}\in\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$,
i.e., there exists $\tau>0$ such that

$R\coloneqq p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{x}_{0}+\tau\bm{x})\leq
p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}}(\bm{x}_{0})=\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}.$

Now, choose $\bm{h}\in\text{B}_{1}^{\smash{d}}$ such that
$R\cdot\bm{D}\bm{h}=\bm{x}_{0}+\tau\bm{x}$ and write
$\bm{x}=\bm{D}\cdot(R/\tau\cdot\bm{h}-1/\tau\cdot\bm{z}_{\ell^{\smash{1}}})\eqqcolon\bm{D}(\bm{\bar{z}})$.
Observe that

$\left\|\bm{z}_{\ell^{\smash{1}}}+\tau\bm{\bar{z}}\right\|_{1}=R\cdot\left\|\bm{h}\right\|_{1}\leq
R\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1},$

and therefore
$\bm{\bar{z}}\in\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})$.

###### Remark A.1

The proof of “$\subseteq$” shows that $\bm{z}_{\ell^{\smash{1}}}$ could be
replaced by any other $\bm{z}_{0}$ with $\bm{x}_{0}=\bm{D}\bm{z}_{0}$, which
is not necessarily a minimal $\ell^{1}$-representer of $\bm{x}_{0}$. Hence,
$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})\subseteq\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{0})$
and
$\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})\subseteq\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1},\bm{z}_{0})$
for any $\bm{z}_{0}$ with $\bm{x}_{0}=\bm{D}\bm{z}_{0}$, with inequality if
$\bm{z}_{0}\in Z_{\ell^{\smash{1}}}$.

###  A.4 Proof of Theorem 3.6 (Coefficient Recovery)

Recalling Proposition 2.3, the goal of the proof is to find a lower bound for
the minimum conic singular value
$\lambda_{\text{min}}\left(\bm{\Phi};C\right)=\inf\left\\{\left\|\bm{\Phi}\bm{z}\right\|_{2}:\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}\right\\}$, where we use the abbreviated
notation
$C\coloneqq\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})$
and $\bm{\Phi}\coloneqq\bm{A}\bm{D}$. Note that by assumption
$\left\|\bm{D}\bm{z}\right\|_{2}\geq\lambda_{\text{min}}\left(\bm{D};C\right)>0$
for all $\bm{z}\in C\cap\mathcal{S}^{\smash{d-1}}$. Thus, we obtain

$\displaystyle\lambda_{\text{min}}\left(\bm{\Phi};C\right)$
$\displaystyle=\inf\left\\{\frac{\left\|\bm{A}\bm{D}\bm{z}\right\|_{2}}{\left\|\bm{D}\bm{z}\right\|_{2}}\left\|\bm{D}\bm{z}\right\|_{2}:\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}\right\\}$ (A.4)
$\displaystyle\geq\lambda_{\text{min}}\left(\bm{D};C\right)\cdot\inf\\{\left\|\bm{A}\bm{x}\right\|_{2}:\bm{x}\in\bm{D}C\cap\mathcal{S}^{\smash{n-1}}\\}.$
(A.5)

Theorem 2.5 now implies that there is a numerical constant $c>0$ such that
with probability at least $1-\text{e}^{-u^{2}/2}$, we have

$\inf\\{\left\|\bm{A}\bm{x}\right\|_{2}:\bm{x}\in\bm{D}C\cap\mathcal{S}^{\smash{n-1}}\\}>\sqrt{m-1}-c\cdot\gamma^{2}\cdot(w_{\wedge}(\bm{D}C)+u).$
(A.6)

Thus, with probability at least $1-\text{e}^{-u^{2}/2}$, we conclude from the
previous steps that

$\lambda_{\text{min}}\left(\bm{\Phi};C\right)>\lambda_{\text{min}}\left(\bm{D};C\right)\cdot\left(\sqrt{m-1}-\sqrt{m_{0}-1}\right).$
(A.7)

The claim of the theorem is then a direct consequence of Proposition 2.3.

###### Remark A.2

The above argumentation may be compared with [CCL19, Theorem 3.1]. We also
show that if $\bm{D}$ is bounded away from 0 on the intersection $S$ of a
closed convex cone $C$ and the sphere, then $\bm{A}\bm{D}$ also stays away
from 0 on $S$ with high probability. However, an important difference is that
our result does not involve $\lambda_{\text{min}}\left(\bm{D};C\right)^{-1}$
as a multiplicative factor in the rate $m_{0}\approx
w^{2}_{\wedge}(\bm{D}\cdot C)$. It therefore allows for a tight description of
the sampling rate in the case of noiseless Gaussian measurements; cf. the
discussion subsequent to Theorem 2.5. Indeed, the numerical experiments of
Section 5.1 reveal that
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}})\right)$
may be very small, while ($\text{BP}_{\smash{\eta=0}}^{\text{\smash{coef}}}$)
still allows for exact recovery from $m\approx
w^{2}_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{\ell^{\smash{1}}}))$
measurements.

###  A.5 Proof of Proposition 3.10 (Stable Recovery)

Let $\bm{z}^{\ast}\in\mathbb{R}^{d}$ be chosen according to (3.8), i.e., it
satisfies $\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{2}\leq\varepsilon$
and $\left\|\bm{z}^{\ast}\right\|_{1}=\left\|\bm{z}_{0}\right\|_{1}$, where
$\bm{z}_{0}$ is any vector with $\bm{x}_{0}=\bm{D}\bm{z}_{0}$. The goal is to
invoke [GKM20, Theorem 6.4] with

$t=\max\left\\{r\cdot\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{2},\frac{2\eta}{\sqrt{m-1}-c\cdot\gamma^{2}\cdot\left(\tfrac{r+1}{r}\cdot(w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}^{\ast}))+1)+u\right)}\right\\}.$
(A.8)

Thus, we need to verify that $t$ satisfies

$t\geq\frac{2\eta}{\sqrt{m-1}-c\cdot\gamma^{2}\cdot\left(w_{t}(\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}};\bm{x}_{0}))+u\right)},$
(A.9)

where $w_{t}$ denotes the _local mean width_ at scale $t>0$; see [GKM20,
Definition 6.1] for details on this notion. To that end, we first observe that

$\displaystyle
w_{t}(\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}};\bm{x}_{0}))$
$\displaystyle\leq
w_{t}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0}-\bm{x}_{0})$
(A.10) $\displaystyle\stackrel{{\scriptstyle\mathllap{t\geq
r\cdot\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{2}}}}{{\leq}}w_{r\cdot\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{2}}((\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0})-\bm{x}_{0}),$
(A.11)

where we have used that
$\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}};\bm{x}_{0})\subseteq\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})$
for any $\bm{z}_{0}$ with $\bm{x}_{0}=\bm{D}\bm{z}_{0}$ in the first step (see
Remark A.1), and the monotonicity of the local mean width in the second step.
Observe that we have
$\bm{D}\bm{z}^{\ast}\in\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0}$,
due to the assumption
$\left\|\bm{z}^{\ast}\right\|_{1}=\left\|\bm{z}_{0}\right\|_{1}$. Hence, we
can make use of [GKM20, Lemma A.2] for
$K=\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0}$ in
order to obtain

$\displaystyle
w_{r\cdot\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{2}}((\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0})-\bm{x}_{0})$
$\displaystyle\leq\frac{r+1}{r}\cdot\left(w_{\wedge}((\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0})-\bm{D}\bm{z}^{\ast})+1\right)$
(A.12)
$\displaystyle=\frac{r+1}{r}\cdot(w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}^{\ast}))+1),$
(A.13)

where the equality follows from:

$\displaystyle\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0})+\bm{x}_{0}-\bm{D}\bm{z}^{\ast}$
$\displaystyle=\bm{D}\cdot\\{\bm{h}\in\mathbb{R}^{d}:\left\|\bm{z}_{0}+\bm{h}\right\|_{1}\leq\underbrace{\left\|\bm{z}_{0}\right\|_{1}}_{=\left\|\bm{z}^{\ast}\right\|_{1}}\\}+\bm{x}_{0}-\bm{D}\bm{z}^{\ast}$
(A.14)
$\displaystyle\stackrel{{\scriptstyle\mathllap{\bm{h}^{\prime}=\bm{h}+\bm{z}_{0}-\bm{z}^{\ast}}}}{{=}}\bm{D}\cdot\\{\bm{h}^{\prime}\in\mathbb{R}^{d}:\left\|\bm{z}^{\ast}+\bm{h}^{\prime}\right\|_{1}\leq\left\|\bm{z}^{\ast}\right\|_{1}\\}=\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}^{\ast}).$
(A.15)

We conclude that

$\displaystyle t$
$\displaystyle\geq\frac{2\eta}{\sqrt{m-1}-c\cdot\gamma^{2}\cdot\left(\tfrac{r+1}{r}\cdot(w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}^{\ast}))+1)+u\right)}$
(A.16)
$\displaystyle\geq\frac{2\eta}{\sqrt{m-1}-c\cdot\gamma^{2}\cdot\left(w_{t}(\mathcal{D}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}};\bm{x}_{0}))+u\right)}.$
(A.17)

Hence, [GKM20, Theorem 6.4] then implies that any minimizer of
($\text{BP}_{\eta}^{\text{\smash{sig}}}$) satisfies
$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\leq t$.444This argument does
actually not cover the case of $\eta=0$, but here we can simply use that
$t=r\cdot\left\|\bm{x}_{0}-\bm{D}\bm{z}^{\ast}\right\|_{1}>0$ if
$\bm{x}_{0}\neq\bm{D}\bm{z}^{\ast}$.

##  Appendix B Proof of Proposition 4.3 (Width and Condition Number)

Let us start with a preliminary lemma, which generalizes Proposition 10.2 in
[ALMT14].

###### Lemma B.1

For a closed convex cone $C\subseteq\mathbb{R}^{d}$, a dictionary
$\bm{D}\in\mathbb{R}^{n\times d}$ and a standard Gaussian vector
$\bm{g}\sim\mathcal{N}(\bm{0},\bm{Id}_{n})$, we have that

$\mathbb{E}\left[\left(\sup_{\bm{z}\in
C\cap\text{B}_{2}^{\smash{d}}}\left\langle\bm{g},\bm{D}\bm{z}\right\rangle\right)^{2}\right]\leq\left(\mathbb{E}\left[\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\left\langle\bm{g},\bm{D}\bm{z}\right\rangle\right]\right)^{2}+\lambda^{2}_{\text{max}}\left(\bm{D};C\right).$
(B.1)

###### Proof.

Define the random variable $Z=Z(\bm{g}):=\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{g},\bm{D}\bm{z}\rangle$. In a first
step, we prove that

$\displaystyle\mathbb{E}\left[\left(\sup_{\bm{z}\in
C\cap\text{B}_{2}^{\smash{d}}}\langle\bm{g},\bm{D}\bm{z}\rangle\right)^{2}\right]\leq\mathbb{E}\left[Z^{2}\right].$
(B.2)

Indeed, since $Z^{2}$ is a nonnegative random variable, we obtain

$\displaystyle\mathbb{E}[Z^{2}]\geq\mathbb{E}\left[Z^{2}\cdot\mathbf{1}_{\mathbb{R}^{d}\backslash
C^{\circ}}(\bm{D}^{*}\bm{g})\right]=\mathbb{E}\left[\left(\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{g},\bm{D}\bm{z}\rangle\right)^{2}\cdot\mathbf{1}_{\mathbb{R}^{d}\backslash
C^{\circ}}(\bm{D}^{*}\bm{g})\right],$

where $C^{\circ}$ denotes the _polar cone_ of $C$. Furthermore, it holds true
that

$\displaystyle\mathbb{E}\left[\left(\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{g},\bm{D}\bm{z}\rangle\right)^{2}\cdot\mathbf{1}_{\mathbb{R}^{d}\backslash
C^{\circ}}(\bm{D}^{*}\bm{g})\right]=\mathbb{E}\left[\left(\sup_{\bm{z}\in
C\cap\text{B}_{2}^{\smash{d}}}\langle\bm{g},\bm{D}\bm{z}\rangle\right)^{2}\right].$

Indeed, for an $\bm{x}\in\mathbb{R}^{n}$ such that $\bm{D}^{*}\bm{x}\notin
C^{\circ}$ the equality $\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{x},\bm{D}\bm{z}\rangle=\sup_{\bm{z}\in
C\cap\text{B}_{2}^{\smash{d}}}\langle\bm{x},\bm{D}\bm{z}\rangle$ holds true,
because the supremum over the ball occurs at a vector of length 1. On the
other hand, when $\bm{D}^{*}\bm{x}\in C^{\circ}$, one has $\sup_{\bm{z}\in
C\cap\text{B}_{2}^{\smash{d}}}\langle\bm{x},\bm{D}\bm{z}\rangle=0$. Therefore,
(B.2) is established.

Moreover, observe that the function $\bm{g}\mapsto Z(\bm{g})$ is
$\lambda_{\max}(\bm{D},C)$-Lipschitz. Indeed, for
$\bm{f},\bm{g}\in\mathbb{R}^{n}$ and $\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}$ we obtain that

$\displaystyle\langle\bm{g},\bm{D}\bm{z}\rangle$
$\displaystyle=\langle\bm{f},\bm{D}\bm{z}\rangle+\langle\bm{g},\bm{D}\bm{z}\rangle-\langle\bm{f},\bm{D}\bm{z}\rangle\leq\langle\bm{f},\bm{D}\bm{z}\rangle+\left\|\bm{f}-\bm{g}\right\|_{2}\left\|\bm{D}\bm{z}\right\|_{2}$
$\displaystyle\leq\langle\bm{f},\bm{D}\bm{z}\rangle+\lambda_{\max}(\bm{D},C)\left\|\bm{f}-\bm{g}\right\|_{2},$

and therefore by taking the supremum

$\displaystyle\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{g},\bm{D}\bm{z}\rangle\leq\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\langle\bm{f},\bm{D}\bm{z}\rangle+\lambda_{\max}(\bm{D},C)\left\|\bm{f}-\bm{g}\right\|_{2}.$

By swapping the roles of $\bm{f}$ and $\bm{g}$, an analogue estimate can be
obtained, which verifies the claimed Lipschitz continuity. Thus, the
fluctuation of $Z$ can be bounded as follows:

$\displaystyle\mathbb{E}\left[Z^{2}\right]-\mathbb{E}\left[Z\right]^{2}=\mathbb{E}\left[(Z-\mathbb{E}Z)^{2}\right]=\text{Var}(Z)\leq\lambda^{2}_{\max}(\bm{D},C),$

where the last estimate follows from Fact C.3 in [ALMT14]. ∎

##### Back to the proof of Proposition 4.3.

In order to prove Proposition 4.3, we continue as follows: First observe that

$w^{2}_{\wedge}(\bm{D}\cdot C)=w^{2}(\bm{D}\cdot
C\cap\mathcal{S}^{\smash{n-1}})\leq\delta(\bm{D}\cdot
C)=\mathbb{E}\left[\left(\sup_{\bm{x}\in\bm{D}\cdot
C\cap\text{B}_{2}^{\smash{n}}}\left\langle\bm{g},\bm{x}\right\rangle\right)^{2}\right],$
(B.3)

where $\delta$ denotes the _statistical dimension_ 555The statistical
dimension of a convex cone $C\subseteq\mathbb{R}^{n}$ can be defined as
$\delta(C)=\mathbb{E}[(\sup_{\bm{x}\in
C\cap\text{B}_{2}^{\smash{n}}}\left\langle\bm{g},\bm{x}\right\rangle)^{2}]$;
see [ALMT14, Prop. 3.1] for details. It holds true that
$w^{2}_{\wedge}(C)\leq\delta(C)\leq w^{2}_{\wedge}(C)+1$, which is why both
notions are often interchangeable [ALMT14, Prop. 10.2].. Next, it is
straightforward to see that

$\bm{D}\cdot
C\cap\text{B}_{2}^{\smash{n}}\subseteq\frac{\bm{D}}{\lambda_{\text{min}}\left(\bm{D};C\right)}\cdot\left(C\cap\text{B}_{2}^{\smash{d}}\right),$
(B.4)

which immediately implies that

$\delta(\bm{D}\cdot
C)\leq\frac{1}{\lambda^{2}_{\text{min}}\left(\bm{D};C\right)}\cdot\mathbb{E}\left[\left(\sup_{\bm{x}\in\bm{D}\left(C\cap\text{B}_{2}^{\smash{d}}\right)}\left\langle\bm{g},\bm{x}\right\rangle\right)^{2}\right].$
(B.5)

Exercise 7.5.4 in [Ver18] and Lemma B.1 now allow us to derive the desired
bound:

$\displaystyle w^{2}_{\wedge}(\bm{D}\cdot C)\leq\delta(\bm{D}\cdot C)$
$\displaystyle\leq\frac{1}{\lambda^{2}_{\text{min}}\left(\bm{D};C\right)}\mathbb{E}\left[\left(\sup_{\bm{x}\in\bm{D}\left(C\cap\text{B}_{2}^{\smash{d}}\right)}\left\langle\bm{g},\bm{x}\right\rangle\right)^{2}\right]$
(B.6)
$\displaystyle\stackrel{{\scriptstyle(\ref{lem:statdim})}}{{\leq}}\frac{1}{\lambda^{2}_{\text{min}}\left(\bm{D};C\right)}\left(\left(\mathbb{E}\left[\sup_{\bm{x}\in\bm{D}\left(C\cap\mathcal{S}^{\smash{d-1}}\right)}\left\langle\bm{g},\bm{x}\right\rangle\right]\right)^{2}+\lambda^{2}_{\text{max}}\left(\bm{D};C\right)\right)$
(B.7)
$\displaystyle\stackrel{{\scriptstyle(7.5.4)}}{{\leq}}\frac{\left\|\bm{D}\right\|_{2}^{2}}{\lambda^{2}_{\text{min}}\left(\bm{D};C\right)}\left(\left(\mathbb{E}\left[\sup_{\bm{z}\in
C\cap\mathcal{S}^{\smash{d-1}}}\left\langle\bm{g},\bm{z}\right\rangle\right]\right)^{2}+1\right)$
(B.8)
$\displaystyle=\kappa^{2}_{{\bm{D},C}}\cdot\left(w^{2}_{\wedge}(C)+1\right).$
(B.9)

##  Appendix C Proofs of Section 4.2

###  C.1 Proof of Proposition 4.7 (Circumangle of Polyhedral Cones)

Consider a nontrivial pointed polyhedral cone
$C=\mathrm{cone}(\bm{x}_{1},\ldots,\bm{x}_{k})$ with
$\left\|\bm{x}_{i}\right\|_{2}=1$ for $i\in[k]$ and let $\alpha$ denote its
circumangle. Let
$\bm{X}\coloneqq[\bm{x}_{1},\ldots,\bm{x}_{k}]\in\mathbb{R}^{n\times k}$.
Since $C$ does not contain a line, its circumcenter $\bm{\theta}$ is unique,
belongs to the cone and $0\leq\alpha<\pi/2$, see [HS10]. This implies that
$\bm{X}^{*}\bm{\theta}>\bm{0}$ (element-wise). We have:

$\displaystyle\cos(\alpha)$
$\displaystyle=\sup_{\bm{v}\in\mathcal{S}^{\smash{n-1}}}\inf_{\bm{x}\in
C\cap\mathcal{S}^{\smash{n-1}}}\langle\bm{x},\bm{v}\rangle=\sup_{\bm{v}\in\mathcal{S}^{\smash{n-1}}}\inf_{\bm{c}\geq\bm{0},\left\|\bm{X}\bm{c}\right\|_{2}^{2}=1}\langle\bm{X}\bm{c},\bm{v}\rangle$
$\displaystyle\leq\sup_{\bm{v}\in\mathcal{S}^{\smash{n-1}}}\inf_{i\in[k]}\langle\bm{e}_{i},\bm{X}^{*}\bm{v}\rangle=\sup_{\bm{v}\in\mathcal{S}^{\smash{n-1}}}\min\bm{X}^{*}\bm{v},$

where $\bm{e}_{i}$ denotes $i$-th standard basis vector in $\mathbb{R}^{k}$
and we have used an inclusion of sets argument in the inequality. We now argue
that the inequality is in fact an equality. To that end, observe that for any
$\bm{v}\in\mathcal{S}^{\smash{n-1}}$ such that $\bm{X}^{*}\bm{v}\geq 0$, we
also have that

$\displaystyle\inf_{\bm{c}\geq\bm{0},\left\|\bm{X}\bm{c}\right\|_{2}^{2}=1}\langle\bm{c},\bm{X}^{*}\bm{v}\rangle\geq\inf_{\bm{c}\geq\bm{0},\left\|\bm{X}\bm{c}\right\|_{2}^{2}\geq
1}\langle\bm{c},\bm{X}^{*}\bm{v}\rangle\geq\inf_{\bm{c}\geq\bm{0},\langle\mathbbm{1},\bm{c}\rangle\geq
1}\langle\bm{c},\bm{X}^{*}\bm{v}\rangle=\min\bm{X}^{*}\bm{v}.$

In this sequence of inequalities, we first used the inclusion of sets, the
triangular inequality together with the inclusion of sets and finally the fact
that a linear program attains its minimum (if it exists) on an extremal point
$\mathrm{Ext}\left(\\{\bm{c}\geq 0,\langle\mathbbm{1},\bm{c}\rangle\geq
1\\}\right)=\\{\bm{e}_{1},\ldots,\bm{e}_{k}\\}$. Note that the condition
$\bm{X}^{*}\bm{v}\geq 0$ ensures the existence of a solution.

Finally the infimum over $\mathcal{S}^{\smash{n-1}}$ can be relaxed to
$\text{B}_{2}^{\smash{n}}$, since the supremum is attained on the boundary of
the domain. This concludes the proof.

###  C.2 Proof of Proposition 4.9 (Maximal Width of Polyhedral Cones)

The proof of Proposition 4.9 necessitates a basic preliminary result on the
Gaussian width of general convex polytopes, which we will proof first.

##### Bounding the Gaussian Width of Convex Polytopes

###### Lemma C.1

Let $K$ be a convex polytope with $k\geq 5$ vertices that is contained in the
unit ball of $\mathbb{R}^{n}$. Then:

$\displaystyle w(K)$
$\displaystyle\leq\sqrt{2\log\left(\frac{k}{\sqrt{2\pi}}\right)}+\frac{1}{\sqrt{2\log\left(\frac{k}{\sqrt{2\pi}}\right)}}.$

###### Proof.

Denote by $\mathcal{V}(K)$ the set of vertices of $K$. Since the maximum of
the scalar products with points of a convex set is attained on a vertex, we
get the following union bound for $x>0$ and
$\bm{g}\sim\mathcal{N}(\bm{0},\operatorname{\textbf{Id}})$:

$\displaystyle\mathbb{P}\left[\sup_{\bm{u}\in
K}\langle\bm{u},\bm{g}\rangle\geq x\right]$
$\displaystyle\leq\sum_{\bm{v}\in\mathcal{V}(K)}\mathbb{P}\left[\langle\bm{v},\bm{g}\rangle\geq
x\right]$
$\displaystyle\leq\sum_{\bm{v}\in\mathcal{V}(K)}\tfrac{1}{\sqrt{2\pi}\left\lVert\bm{v}\right\rVert_{2}}\int_{x}^{\infty}\exp\left(-\frac{y^{2}}{2\left\lVert\bm{v}\right\rVert_{2}^{2}}\right)\mathrm{d}y$
(C.1)
$\displaystyle\leq\tfrac{k}{\sqrt{2\pi}}\cdot\int_{x}^{\infty}\exp\left(-\tfrac{y^{2}}{2}\right)\mathrm{d}y.$
(C.2)

Recall the following standard bound on the tail probability of a Gaussian,
which will be used in the remainder of the proof:

$\displaystyle\int_{x}^{\infty}\exp(-y^{2}/2)\mathrm{d}y$
$\displaystyle\leq\frac{\exp(-x^{2}/2)}{x}.$

Let $x_{0}\coloneqq\sqrt{2\log\left(\frac{k}{\sqrt{2\pi}}\right)}>1$ and note
that $\frac{k}{\sqrt{2\pi}}\exp\left(-\frac{x_{0}^{2}}{2}\right)=1$. We may
now use the bound (C.2) in order to obtain:

$\displaystyle w(K)$
$\displaystyle\leq\int_{\mathbb{R}_{+}}\mathbb{P}\left[\sup_{\bm{u}\in
K}\langle\bm{u},\bm{g}\rangle\geq x\right]\mathrm{d}x$
$\displaystyle\leq\int_{\mathbb{R}_{+}}\min\left\\{1,\frac{k}{\sqrt{2\pi}}\int_{x}^{\infty}\exp\left(-\frac{y^{2}}{2}\right)\mathrm{d}y\right\\}\mathrm{d}x$
$\displaystyle\leq
x_{0}+\frac{k}{\sqrt{2\pi}}\int_{x_{0}}^{\infty}\exp\left(-\frac{x^{2}}{2}\right)\mathrm{d}x$
$\displaystyle\leq x_{0}+\frac{1}{x_{0}}.$

∎

##### Back to the proof of Proposition 4.9

Equipped with this lemma, we can now prove Proposition 4.9.

Let $C=\operatorname{cone}(\bm{x}_{1},\dots,\bm{x}_{k})\subset\mathbb{R}^{n}$
be a $k$-polyhedral $\alpha$-cone and let
$\bm{\theta}\in\mathcal{S}^{\smash{n-1}}$ be an axis vector such that
$C\subseteq C(\alpha,\bm{\theta})$. Without loss of generality assume that
$\left\|\bm{x}_{i}\right\|_{2}=1$ for $i\in[k]$. Define the affine hyperplane
$\mathcal{H}\coloneqq\left\\{\bm{h}\in\mathbb{R}^{n}:\left\langle\bm{h},\bm{\theta}\right\rangle=1\right\\}$
and let $K\coloneqq C\cap\mathcal{H}$. Observe that $K$ is a convex polyhedron
with vertices belonging to the set
$\left\\{\bm{x}_{i}/\left\langle\bm{x}_{i},\bm{\theta}\right\rangle:i\in[k]\right\\}\subseteq\text{B}_{2}^{\smash{n}}(\cos(\alpha)^{-1})$.
Since $\left\|\bm{k}\right\|_{2}\geq 1$ for all $\bm{k}\in K$, any $\bm{h}\in
C\cap\mathcal{S}^{\smash{n-1}}$ can be written as
$\bm{h}=\lambda(\bm{k})\cdot\bm{k}$, where $\bm{k}\in K$ and
$0<\lambda(\bm{k})\leq 1$. Hence, for all $\bm{g}\in\mathbb{R}^{n}$ it holds
true that

$\sup_{\bm{h}\in\mathcal{S}^{\smash{n-1}}\cap
C}\left\langle\bm{h},\bm{g}\right\rangle=\sup_{\bm{k}\in
K}\left(\lambda(\bm{k})\cdot\left\langle\bm{k},\bm{g}\right\rangle\right)\leq\max\left\\{0,\sup_{\bm{k}\in
K}\left\langle\bm{k},\bm{g}\right\rangle\right\\}.$ (C.3)

Let $\bm{P}^{\bm{\theta}},\bm{P}_{\perp}^{\bm{\theta}}$ denote the orthogonal
projections onto $\operatorname{\operatorname{span}}{(\bm{\theta})}$ and
$\operatorname{\operatorname{span}}{(\bm{\theta})}^{\perp}$, respectively.
Observe that for $\bm{k}\in K$ and $\bm{g}\in\mathbb{R}^{n}$ it holds true
that

$\left\langle\bm{k},\bm{g}\right\rangle=\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle+\left\langle\bm{P}_{\perp}^{\bm{\theta}}(\bm{k}),\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle\leq\max\left\\{0,\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle\right\\}+\left\langle\bm{P}_{\perp}^{\bm{\theta}}(\bm{k}),\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle,$
(C.4)

where the first equality follows from
$\bm{P}^{\bm{\theta}}(\bm{k})=\bm{\theta}$. Furthermore, since $\bm{\theta}\in
C$, we have that $\bm{0}\in\bm{P}_{\perp}^{\bm{\theta}}(K)$ and hence for all
$\bm{g}\in\mathbb{R}^{n}$,

$\sup_{\bm{k}\in
K}\left\langle\bm{P}_{\perp}^{\bm{\theta}}(\bm{k}),\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle\geq
0.$ (C.5)

This allows us to conclude that

$\sup_{\bm{h}\in\mathcal{S}^{\smash{n-1}}\cap
C}\left\langle\bm{h},\bm{g}\right\rangle\leq\max\left\\{0,\sup_{\bm{k}\in
K}\left\langle\bm{k},\bm{g}\right\rangle\right\\}\leq\max\left\\{0,\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle\right\\}+\sup_{\bm{k}\in
K}\left\langle\bm{P}_{\perp}^{\bm{\theta}}(\bm{k}),\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle.$
(C.6)

Hence, we obtain

$\displaystyle w_{\wedge}(C)$
$\displaystyle=\mathbb{E}_{n}\left[\sup_{\bm{h}\in\mathcal{S}^{\smash{n-1}}\cap
C}\left\langle\bm{h},\bm{g}\right\rangle\right]$ (C.7)
$\displaystyle=\mathbb{E}_{n}\left[\max\left\\{0,\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle\right\\}+\sup_{\bm{k}\in
K}\left\langle\bm{P}_{\perp}^{\bm{\theta}}(\bm{k}),\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle\right]$
(C.8)
$\displaystyle=\mathbb{E}_{1}\left[\max\left\\{0,\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle\right\\}\right]+\mathbb{E}_{n-1}\left[\sup_{\bm{k}\in\bm{P}_{\perp}^{\bm{\theta}}(K)}\left\langle\bm{k},\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})\right\rangle\right]$
(C.9)
$\displaystyle=\frac{1}{\sqrt{2\pi}}+w(\bm{P}_{\perp}^{\bm{\theta}}(K)),$
(C.10)

where the last equality follows from
$\left\langle\bm{\theta},\bm{P}^{\bm{\theta}}(\bm{g})\right\rangle\sim\mathcal{N}(0,1)$
and the fact that $\bm{P}_{\perp}^{\bm{\theta}}(\bm{g})$ is an
$(n-1)$-dimensional standard Gaussian vector on
$\operatorname{\operatorname{span}}{(\bm{\theta})}^{\perp}$.

Since $K\subset\mathcal{H}\cap\text{B}_{2}^{\smash{n}}(\cos(\alpha)^{-1})$,
its $(n-1)$-dimensional projection satisfies
$\bm{P}_{\perp}^{\bm{\theta}}(K)\subset\text{B}_{2}^{\smash{n-1}}(\tan(\alpha))$.
Now, Lemma C.1 yields the following bound on the Gaussian width of a
polyhedron included in a ball of radius $\tan\alpha$ with at most $k\geq 5$
vertices:

$w(\bm{P}_{\perp}^{\bm{\theta}}(K))\leq{\tan\alpha}\cdot\left(\sqrt{2\log(k/\sqrt{2\pi})}+1/\sqrt{2\log(k/\sqrt{2\pi})}\right).$
(C.11)

The claimed inequality of Proposition 4.9 is then just a consequence of
(C.10).

###  C.3 Proofs of Section 4.2.2

##### Descent Cone of $\ell^{1}$-Norm (Lemma 4.11)

We begin by showing a polyhedral description of the descent cone of the
$\ell^{1}$-norm:

Let $\bm{v}$ be any vector such that $\|\bm{v}\|_{1}=s$ and
$\operatorname{sign}\bm{v}=\operatorname{sign}\bm{z}$. Note that $\bm{v}$ and
$\bm{z}$ enjoy the same descent cone associated to the $\ell^{1}$-norm, which
is easy to see by observing that

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})=\left\\{\bm{h}\in\mathbb{R}^{d}:\sum_{i\in\mathcal{S}^{c}}\left\lvert
h_{i}\right\rvert\leq-\sum_{i\in\mathcal{S}}\operatorname{sign}(z_{i})\cdot
h_{i}\right\\}.$ (C.12)

Therefore, the descent set of $\|\cdot\|_{1}$ at $\bm{v}$ can be obtained by
scaling up the cross-polytope by the factor $\|\bm{v}\|_{1}=s$ and shifting it
by $-\bm{v}$, i.e.,

$\mathcal{D}(\left\|\cdot\right\|_{1},\bm{v})=\operatorname{conv}(\pm
s\cdot\bm{e}_{i}-\bm{v}:i\in[d]).$

We conclude by taking the conic hull of the previous set to obtain

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})=\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{v})=\operatorname{cone}(\pm
s\cdot\bm{e}_{i}-\bm{v}:i\in[d]).$

##### Lineality of Descent Cone of $\ell^{1}$-Norm (Lemma 4.13)

Next, we describe the lineality space and lineality of
$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})$:

The lineality space of the descent cone at point $\bm{z}$ corresponds to the
span of the face of the $\ell^{1}$-ball of minimal dimension containing
$\bm{z}$. It can therefore be defined as the span of the vectors joining
$\bm{z}$ to the vertices of this face, which are exactly the vectors
$\operatorname{sign}(z_{i})\cdot\bm{e}_{i}$.

For a more formal proof for this fact, one could argue as follows: First note
that (see for instance Appendix B in [ALMT14])

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})^{\circ}=\bigcup_{\tau\geq
0}\tau\cdot\partial\left\|\bm{z}\right\|_{1}.$ (C.13)

Since
$\partial\left\|\bm{z}\right\|_{1}=\left\\{\bm{h}\in\mathbb{R}^{d}:\bm{h}_{\mathcal{S}}=\operatorname{sign}(\bm{z})_{\mathcal{S}},\bm{h}_{\mathcal{S}^{c}}\in[-1,1]^{d-s}\right\\}$,
it follows that the polar cone is closed, pointed (i.e.,
$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})^{\circ}\cap-\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})^{\circ}=\left\\{\bm{0}\right\\}$)
and therefore finitely generated by its extreme rays

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})^{\circ}=\operatorname{cone}(\bm{z}^{j}\in\mathbb{R}^{d}:j\in[2^{d-s}]),$
(C.14)

where $\bm{z}^{j}_{\mathcal{S}}=\operatorname{sign}(\bm{z})_{\mathcal{S}}$ and
on $\mathcal{S}^{c}$ all $2^{d-s}$ combinations
$\bm{z}^{j}_{\mathcal{S}^{c}}=\left\\{-1,1\right\\}^{d-s}$. Hence, we obtain
the following polyhedral description for the descent cone

$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})=\left\\{\bm{h}\in\mathbb{R}^{d}:\left\langle\bm{h},\bm{z}^{j}\right\rangle\leq
0\mbox{ for all }j\in[2^{d-s}]\right\\}.$ (C.15)

Using the matrix
$\bm{B}\coloneqq\left[\bm{z}^{1},\dots,\bm{z}^{2^{d-s}}\right]^{T}\in\mathbb{R}^{2^{d-s}\times
d}$, the lineality space can then be conveniently expressed as
$L_{\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})}=\ker(\bm{B})$.

On the other hand, observe that for any $\bm{h}\in
L_{\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})}$, we can find
$\tau>0$ such that
$\left\|\bm{z}+\tau\cdot\bm{h}\right\|_{1}\leq\left\|z\right\|_{1}$ and
therefore (by choosing $\tau>0$ small enough)

$\sum_{j\in\mathcal{S}}\operatorname{sign}(z_{j})\cdot(z_{j}+\tau\cdot
h_{j})+\sum_{i\in\mathcal{S}^{c}}|h_{i}|\leq\sum_{j\in\mathcal{S}}|z_{j}|.$
(C.16)

Similarly, since also
$-\bm{h}\in\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})$, we obtain
(again by choosing a small enough $\tau>0$)

$\sum_{j\in\mathcal{S}}\operatorname{sign}(z_{j})\cdot(z_{j}-\tau\cdot
h_{j})+\sum_{i\in\mathcal{S}^{c}}|h_{i}|\leq\sum_{j\in\mathcal{S}}|z_{j}|.$
(C.17)

Adding up these two inequalities, we obtain that
$\sum_{i\in\mathcal{S}^{c}}|h_{i}|\leq 0$ and hence $h_{i}=0$ for all
$i\in\mathcal{S}^{c}$.

Combining this fact with the previous observation, we obtain that

$L_{\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z})}=\left\\{\bm{h}\in\mathbb{R}^{d}:\bm{h}_{\mathcal{S}^{c}}=\bm{0},\left\langle\operatorname{sign}(\bm{z}),\bm{h}\right\rangle=0\right\\},$
(C.18)

which is of dimension $s-1$. From this description, we can conclude that for
each $i\in\mathcal{S}$ the vector
$s\cdot\operatorname{sign}(z_{i})\cdot\bm{e}_{i}-\operatorname{sign}(\bm{z})$
is contained in the later space. Hence, if we can show that

$\dim\left(\operatorname{\operatorname{span}}\left(s\cdot\operatorname{sign}(z_{i})\cdot\bm{e}_{i}-\operatorname{sign}(\bm{z}):i\in\mathcal{S}\right)\right)=s-1,$
(C.19)

we have succeeded in proving the lemma. Indeed, consider the matrix
$\bm{C}\in\mathbb{R}^{s\times s-1},$ where the columns are formed by
$\left(s\cdot\operatorname{sign}(z_{i})\cdot\bm{e}_{i}-\operatorname{sign}(\bm{z})\right)_{\mathcal{S}},$
for each $i\in\mathcal{S}$, except for one. Then, the matrix
$\bm{C}^{T}\cdot\bm{C}\in\mathbb{R}^{s-1\times s-1}$ has the value $s^{2}-s$
on its diagonal and $-s$ everywhere else. Thus it is strictly diagonal
dominant and invertible, implying that $\bm{C}$ is of full rank, as desired.

##### Lineality and Range for Gauge (Proposition 4.16)

Lastly, we characterize the range and lineality of
$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$:

First, observe that a combination of Lemma 3.5 and Lemma 4.11 yields that

$\displaystyle\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$
$\displaystyle=\bm{D}\cdot\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})$
(C.20)
$\displaystyle=\bm{D}\cdot\operatorname{cone}(\pm\bar{s}\cdot\bm{e}_{i}-\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}):i\in[d])$
(C.21)
$\displaystyle=\operatorname{cone}(\pm\bar{s}\cdot\bm{d}_{i}-\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}):i\in[d]).$
(C.22)

By Lemma 4.13, we know how to characterize the lineality of
$\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})$.
Note that for any convex set $C\subseteq\mathbb{R}^{d}$, it holds true that
$\left({\bm{D}\cdot C}\right)_{L}\supseteq\bm{D}\cdot C_{L}$, however, the
reverse inclusion is not satisfied, in general. Hence, Lemma 3.5 immediately
implies
$\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}\supseteq\bm{D}\cdot\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$.
For proving the reverse inclusion
$\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}\subseteq\bm{D}\cdot\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$,
we will now show that if
${\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}\not\subseteq\bm{D}\cdot\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}}$,
then $\bm{z}_{\ell^{\smash{1}}}$ did not have maximal support. To that end,
pick any vector
$\bm{x}\in\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}\setminus\bm{D}\cdot\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$
and write $\bm{x}=\bm{D}\cdot\bm{z}^{1}$, where
$\bm{z}^{1}\in\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\setminus\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$.
Since
$\bm{x}\in\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}$,
we can also chose a
$\bm{z}^{2}\in\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\setminus\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$
with $-\bm{x}=\bm{D}\cdot\bm{z}^{2}$. Due to
$\bm{z}^{i}\not\in\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}$
for $i=1,2$, we have that for all $\varepsilon>0$

$\left\|\bm{z}_{\ell^{\smash{1}}}-\varepsilon\cdot\bm{z}^{i}\right\|_{1}>\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1},$
(C.23)

however, there exists a small enough $\varepsilon>0$ such that

$\left\|\bm{z}_{\ell^{\smash{1}}}+\varepsilon\cdot\bm{z}^{i}\right\|_{1}\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}.$
(C.24)

For small enough $\varepsilon>0$, inequality (C.23) implies that

$\sum_{j\in\bar{\mathcal{S}}}\operatorname{sign}(z_{\ell^{1},j})\cdot
z^{i}_{j}-\sum_{j\in\bar{\mathcal{S}}^{c}}|z^{i}_{j}|<0,$ (C.25)

whereas (C.24) means that

$\sum_{j\in\bar{\mathcal{S}}}\operatorname{sign}(z_{\ell^{1},j})\cdot
z^{i}_{j}+\sum_{j\in\bar{\mathcal{S}}^{c}}|z^{i}_{j}|\leq 0.$ (C.26)

Summing up the previous two inequalities, we obtain that
$\sum_{j\in\bar{\mathcal{S}}}\operatorname{sign}(z_{\ell^{1},j})\cdot(z^{1}_{j}+z^{2}_{j})<0$.
Now, define
$\bm{z}^{\delta}\coloneqq\bm{z}_{\ell^{\smash{1}}}+\delta\cdot(\bm{z}^{1}+\bm{z}^{2})$
and observe that for all $\delta>0$ it holds true that
$\bm{x}=\bm{D}\cdot\bm{z}^{\delta}$. Furthermore, for a small enough
$\delta>0$, we have that
$\left\|\bm{z}^{\delta}\right\|_{1}\leq\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}$.
Hence, we can conclude that $\bm{z}^{\delta}\in Z_{\ell^{\smash{1}}}$ and
therefore even
$\left\|\bm{z}^{\delta}\right\|_{1}=\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}$.
If $\delta>0$ is chosen small enough, this allows us to write

$\left\|\bm{z}^{\delta}\right\|_{1}=\left\|\bm{z}_{\ell^{\smash{1}}}\right\|_{1}+\delta\cdot\sum_{j\in\bar{\mathcal{S}}}\operatorname{sign}(z_{\ell^{1},j})\cdot(z^{1}_{j}+z^{2}_{j})+\delta\cdot\sum_{j\in\bar{\mathcal{S}}^{c}}|z^{1}_{j}+z^{2}_{j}|,$
(C.27)

and we can conclude that
$\sum_{j\in\bar{\mathcal{S}}^{c}}|z^{1}_{j}+z^{2}_{j}|>0$. However, this means
that there is at least one $j\in\bar{\mathcal{S}}^{c}$ such that
$\bm{z}^{\delta}_{j}\neq 0$, which shows that $\bm{z}$ was indeed not maximal.
Finally, Lemma 4.13 implies that

$\dim\left(\left({\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})}\right)_{L}\right)=\dim\left(\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}\right)-\dim\left(\ker\bm{D}_{|\left({\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})}\right)_{L}}\right)\leq\bar{s}-1,$
(C.28)

which concludes the proof of first part of the proposition concerning the
lineality of
$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$.

The characterization of the range follows easily. Indeed, let
$i\in\mathcal{S}$ and consider the vector
$\bm{r}_{i}^{-}=-\bar{s}\cdot\operatorname{sign}(z_{\ell^{1},i})\cdot\bm{d}_{i}-\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}})$.
Observe that we can write
$\bm{r}_{i}^{-}=-2\cdot\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}})-\bm{r}_{i}^{+}$.
Hence, for any $j\in\bar{\mathcal{S}}^{c}\neq\emptyset$ we obtain that

$P_{C_{L}^{\perp}}(\bm{r}_{i}^{-})=-2\cdot
P_{C_{L}^{\perp}}(\bm{D}\cdot\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}))=\bm{r}_{j}^{+\perp}+\bm{r}_{j}^{-\perp}.$
(C.29)

Thus,
$P_{C_{L}^{\perp}}(\bm{r}_{i}^{-})\in\mathrm{cone}(\bm{r}_{j}^{\pm\perp},j\in\bar{\mathcal{S}}^{c})$,
which concludes the proof.

###  C.4 Proof of Theorem 4.17

Let
$C=\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})$
and use the orthogonal decomposition provided in Proposition 4.16:

$\mathcal{D}_{\wedge}(p_{\bm{D}\cdot\text{B}_{1}^{\smash{d}}},\bm{x}_{0})=C_{L}\oplus
C_{R}.$ (C.30)

This allows us to estimate

$w^{2}_{\wedge}(C)\stackrel{{\scriptstyle(1)}}{{\leq}}\delta(C)\stackrel{{\scriptstyle(2)}}{{\leq}}\delta(C_{L})+\delta(C_{R})\stackrel{{\scriptstyle(3)}}{{\leq}}\dim(C_{L})+w^{2}_{\wedge}(C_{R})+1,$
(C.31)

where $\delta$ denotes the _statistical dimension_ ; see proof of Proposition
4.3 in Appendix B for further details on this notion and a justification of
$(1)$. Using the statistical dimension as a summary parameter for convex cones
brings several advantages. For a direct sum $C_{1}\oplus C_{2}$ of two closed
convex cones $C_{1},C_{2}\subseteq\mathbb{R}^{n}$ it holds true that
$\delta(C_{1}\oplus C_{2})=\delta(C_{1})+\delta(C_{2})$, explaining $(2)$ in
the previous inequalities. Furthermore, for a subspace
$C_{L}\subseteq\mathbb{R}^{n}$ we have that $\delta(C_{L})=\dim(C_{L})$,
which, together with $\delta(C_{R})\leq w^{2}_{\wedge}(C_{R})+1$, justifies
$(3)$. Observe that the estimate of (C.31) is essentially tight.

Proposition 4.16 allows to upper bound $\dim(C_{L})+1$ by $\bar{s}$. The
statement then follows by applying Proposition 4.9 to the
$2(d-\bar{s})$-polyhedral $\alpha$-cone $C_{R}$.

###  C.5 Proof of Proposition 4.20 (Coherence Bound)

First, observe that we have

$\displaystyle\tan^{2}\left(\angle(\bm{a},\bm{a}+\bm{b})\right)=\frac{\|\bm{a}\times(\bm{a}+\bm{b})\|_{2}^{2}}{\langle\bm{a},\bm{a}+\bm{b}\rangle^{2}}=\frac{\left\|\bm{a}\right\|_{2}^{2}\left\|\bm{b}\right\|_{2}^{2}-\left\langle\bm{a},\bm{b}\right\rangle^{2}}{\left(\left\|\bm{a}\right\|_{2}^{2}+\left\langle\bm{a},\bm{b}\right\rangle\right)^{2}}$
$\displaystyle\leq\frac{\left\|\bm{a}\right\|_{2}^{2}\left\|\bm{b}\right\|_{2}^{2}}{\left(\left\|\bm{a}\right\|_{2}^{2}+\left\langle\bm{a},\bm{b}\right\rangle\right)^{2}},$
(C.32)

where $\bm{a},\bm{b}\in\mathbb{R}^{n}$ with $\bm{a}\neq 0$ and
$\bm{a}+\bm{b}\neq 0$.

Obsere that the assumptions of Proposition 4.16 are satisfied. Indeed,
$s<\tfrac{1}{2}(1+\mu^{-1}(\bm{D}))$ guarantees that
$\bm{z}_{\ell^{\smash{1}}}$ is the unique minimal $\ell^{1}$-representer of
the associated signal $\bm{D}\bm{z}_{\ell^{\smash{1}}}$ and that
$\bm{D}\bm{z}_{\ell^{\smash{1}}}\neq\bm{0}$ [DE03, GN03]. Hence, we want to
evaluate the circumangle of the cone generated by the vectors
$\bm{r}_{j}^{\pm\perp}=\bm{P}_{C_{L}^{\perp}}(\pm
s\cdot\bm{d}_{j}-\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}))$ for
$j\in S^{c}$, where
$\mathcal{S}=\operatorname{supp}(\bm{z}_{\ell^{\smash{1}}})$. As a proxy for
the circumcenter, we can consider the vector
$\bm{v}=-\bm{P}_{C_{L}^{\perp}}(\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}))$
and therefore obtain:

$\displaystyle\tan^{2}\alpha\leq\sup_{j\in
S^{c}}\tan^{2}(\angle(\bm{v},\bm{r}_{j}^{\pm\perp}))=\sup_{j\in
S^{c}}\tan^{2}\left(\angle(\bm{v},\bm{v}+\bm{P}_{C_{L}^{\perp}}(s\cdot\bm{d}_{j}))\right).$

We can now use the inequality (C.32) with $\bm{a}=\bm{v}$ and
$\bm{b}=s\cdot\bm{P}_{C_{L}^{\perp}}(\bm{d}_{j})$; note that
$\bm{v}\neq\bm{0}$, since otherwise we would have
$\bm{D}\bm{z}_{\ell^{\smash{1}}}=\bm{0}$. The expression (C.32) is decreasing
w.r.t. $\left\|\bm{a}\right\|_{2}^{2}$. Hence, we shall find a lower bound for
$\left\|\bm{v}\right\|_{2}^{2}$. The projection
$\bm{P}_{C_{L}^{\perp}}(\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}))$
can be written as
$\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}})+\bm{w}$ for some vector
$\bm{w}\in C_{L}$. According to the characterization of the lineality space
$C_{L}$ in Proposition 4.16, this amounts to saying that

$\displaystyle\bm{P}_{C_{L}^{\perp}}(\bm{D}\operatorname{sign}(\bm{z}_{\ell^{\smash{1}}}))$
$\displaystyle=\sum_{i\in\mathcal{S}}c_{i}\cdot\operatorname{sign}(z_{\ell^{1},i})\cdot\bm{d}_{i},\,\mbox{
with }\,\sum_{i\in\mathcal{S}}c_{i}=s.$ (C.33)

This yields

$\displaystyle\left\|\bm{v}\right\|_{2}^{2}$
$\displaystyle\geq\inf_{\bm{c}\in\mathbb{R}^{s},\sum_{i\in\mathcal{S}}c_{i}=s}\left\|\sum_{i\in\mathcal{S}}c_{i}\operatorname{sign}(z_{\ell^{1},i})\bm{d}_{i}\right\|_{2}^{2}$
(C.34)
$\displaystyle=\inf_{\bm{c}\in\mathbb{R}^{s},\sum_{i\in\mathcal{S}}c_{i}=s}\|\bm{c}\|_{2}^{2}+\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S},j\neq
i}c_{i}c_{j}\langle\operatorname{sign}(z_{\ell^{1},i})\bm{d}_{i},\operatorname{sign}(z_{\ell^{1},j})\bm{d}_{j}\rangle$
(C.35)
$\displaystyle\geq\inf_{\bm{c}\in\mathbb{R}^{s},\sum_{i\in\mathcal{S}}c_{i}=s}\|\bm{c}\|_{2}^{2}-\mu\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S},j\neq
i}c_{i}c_{j}.$ (C.36)

The optimality conditions for this program yield the existence of a Lagrange
multiplier $\lambda\in\mathbb{R}$ such that $c_{i}-\mu\sum_{j\neq
i}c_{j}+\lambda=0$ and $\sum_{i\in\mathcal{S}}c_{i}=s$, i.e., $c_{i}=1$ for
all $i\in\mathcal{S}$. Plugging this expression in (C.36), we obtain that

$\displaystyle\left\|\bm{v}\right\|_{2}^{2}\geq s-\mu(s\cdot(s-1))\geq s(1-\mu
s).$

Together with the following inequalities:

$\displaystyle|\langle\bm{a},\bm{b}\rangle|$
$\displaystyle=s\left\lvert\left\langle\bm{v},\bm{P}_{C_{L}^{\perp}}\bm{d}_{j}\right\rangle\right\rvert\leq
s\left\lvert\left\langle\bm{v},\bm{d}_{j}\right\rangle\right\rvert\stackrel{{\scriptstyle\eqref{eq:chara}}}{{\leq}}s^{2}\sup_{i\neq
j}|\left\langle\bm{d}_{i},\bm{d}_{j}\right\rangle|=s^{2}\mu,$ (C.37)
$\displaystyle\left\|\bm{b}\right\|_{2}^{2}$
$\displaystyle=s^{2}\left\|\bm{P}_{C_{L}^{\perp}}\bm{d}_{j}\right\|_{2}^{2}\leq
s^{2}\left\|\bm{d}_{j}\right\|_{2}^{2}=s^{2},$ (C.38)

we obtain the desired bound

$\displaystyle\tan^{2}\alpha$
$\displaystyle\leq\frac{\left\|\bm{a}\right\|_{2}^{2}\left\|\bm{b}\right\|_{2}^{2}}{\left(\left\|\bm{a}\right\|_{2}^{2}+\left\langle\bm{a},\bm{b}\right\rangle\right)^{2}}\leq\frac{s(1-\mu
s)\cdot s^{2}}{(s(1-\mu s)-s^{2}\mu)^{2}}=\frac{s(1-\mu s)}{(1-2\mu s)^{2}}.$

##  Appendix D Details on Numerical Experiments

In this subsection, we report on the setup that we have used in all our
numerical experiments.

##### Phase Transition Plots

While our results encompass the more general class of subgaussian
measurements, we only consider the benchmark of Gaussian matrices, as it is
typically done in the compressed sensing literature. When illustrating the
performance of results such as Theorem 3.6, we only report the quantity
$w_{\wedge}(\bm{D}\cdot\mathcal{D}(\left\|\cdot\right\|_{1};\bm{z}_{0}))$,
ignoring for instance the probability parameter $u$, cf. [ALMT14].

##### Some Details on Computations

Unless stated otherwise, we solve the convex recovery programs such as
($\text{BP}_{\eta}^{\text{\smash{coef}}}$) or ($\text{BP}_{\ell^{1}}$) using
the Matlab toolbox cvx [GB14, GB08]. We employ the default settings and set
the precision to best. For creating phase transitions, a solution
$\hat{\bm{x}}$ is considered to be “perfectly recovered” if the error to the
ground truth vector $\bm{x}_{0}$ satisfies
$\left\|\bm{x}_{0}-\hat{\bm{x}}\right\|_{2}\leq 10^{-5}$. This threshold
produces stable transitions and seems to reflect the numerical accuracy of
cvx.

##### Computing the Statistical Dimension

When analyzing the sampling rate predictions of our results, we often report
the conic mean width $w^{2}_{\wedge}(C)=w(C\cap\mathcal{S}^{n-1})$ of a convex
cone $C\subseteq\mathbb{R}^{n}$. We will now briefly sketch how this quantity
is numerically approximated: First recall that the conic mean width is
essentially equivalent to the statistical dimension
$\delta(C)=\mathbb{E}[\sup_{\bm{x}\in
C\cap\text{B}_{2}^{\smash{n}}}\left\|\Pi_{C}(g)\right\|_{2}^{2}]$; cf. the
proof of Proposition 4.3 in Appendix B. Due to the convexity of
$C\cap\text{B}_{2}^{\smash{n}}$, the statistical dimension is preferred over
the conic mean width for numerical simulations. In order to obtain an
approximation of $\delta(C)$, we draw $k$ independent samples
$\bm{g}_{1},\dots,\bm{g}_{k}\sim\mathcal{N}(\bm{0},\operatorname{\textbf{Id}})$
and for each of them we evaluate the projection $\Pi_{C}(\bm{g}_{i})$ using
quadratic programming. Due to a concentration phenomenon of empirical Gaussian
processes, the arithmetic mean over $k=300$ samples yields tight estimates of
$\delta(C)$.

##### Minimal Conic Singular Values

As already mentioned computing
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$
is out of reach in general. In our numerical experiments on coefficient
recovery, we nevertheless provide empirical upper bounds on
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$.
Those are obtained as follows: Let
$\bm{x}_{0}=\bm{D}\cdot\bm{z}_{\ell^{\smash{1}}}$ and consider the perturbed
$\bm{\tilde{x}_{0}}=\bm{x}_{0}+\hat{\bm{e}}$, where
$\hat{\bm{e}}\in\mathbb{R}^{n}$ such that
$\left\|\hat{\bm{e}}\right\|_{2}\leq\hat{\eta}$. We then define
$\hat{\bm{z}}\in\mathbb{R}^{d}$ as a solution of the program

$\min_{\bm{z}\in\mathbb{R}^{d}}\left\|\bm{z}\right\|_{1}\quad\mbox{ s.t.
}\quad\left\|\bm{\tilde{x}_{0}}-\bm{D}\bm{z}\right\|_{2}\leq\hat{\eta}.$ (D.1)

Proposition 2.3 then implies that
$\left\|\bm{z}_{\ell^{\smash{1}}}-\hat{\bm{z}}\right\|_{2}\leq
2\hat{\eta}/\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$.
Rearranging the terms in the previous inequality then yields an upper bound
for
$\lambda_{\text{min}}\left(\bm{D};\mathcal{D}_{\wedge}(\left\|\cdot\right\|_{1},\bm{z}_{\ell^{\smash{1}}})\right)$.
Note thereby that a clever choice of the perturbation $\hat{\bm{e}}$ may
result in a tighter bound.

##### Computing the Circumcenter and the Circumangle

Computing the circumcenter amounts to solving:

$\bm{\theta}\in\operatorname*{argmin}_{\bm{v}\in\text{B}_{2}^{\smash{n}}}\max_{i\in[k]}\langle-\bm{v},\bm{x}_{i}\rangle,$
(D.2)

where the vectors $\bm{x}_{i}$ are the normalized generators of a nontrivial
pointed polyhedral cone; see Proposition 4.7. This problem is closely related
to the so-called _smallest bounding sphere problem_ [Syl57], which has a long
and rich history.

Let $g(\bm{v})=\max_{i\in[k]}\langle-\bm{v},\bm{x}_{i}\rangle$ and $I(\bm{v})$
denote the set of active indices $i$, i.e., the indices satisfying
$g(\bm{v})=-\langle\bm{v},\bm{x}_{i}\rangle$. Then standard convex analysis
results state that $\partial g(\bm{v})=\mathrm{conv}(-\bm{x}_{i},i\in
I(\bm{v}))$ and the optimality conditions read

$\bm{\theta}\in\mathrm{conv}(\bm{x}_{i},i\in I(\bm{\theta}))\qquad\mbox{ with
}\qquad\left\|\bm{\theta}\right\|_{2}=1,$ (D.3)

i.e., the normal cone $\\{-\bm{\theta}\\}$ to the constraint set should
intersect the subdifferential $\partial g(\bm{\theta})$.

Problem (D.2) can be solved globally with projected subgradient descents or
second order cone programming techniques available in _CVX_.