Simon Foucart
Complete papers inventory


  1. S. F., C. Liao, Radius of information for two intersected centered hyperellipsoids and implications in Optimal Recovery from inaccurate data.
    (pdf) (reproducible)

Journal publications

  1. S. F, G. Paouris, Near-optimal estimation of linear functionals with log-concave observation errors.
    Information and Inference, 12/4, 2546--2561, 2023. (doi) (pdf)
  2. S. F., Full recovery from point values: an optimal algorithm for Chebyshev approximability prior.
    Advances in Computational Mathematics, 49, 57, 2023. (doi) (pdf) (reproducible)
  3. S. F., The sparsity of LASSO-type minimizers.
    Applied and Computational Harmonic Analysis, 62, 441--452, 2023. (doi) (pdf)
  4. B. Deregowska, M. Fickus, S. F., B. Lewandowska, On the value of the fifth maximal projection constant.
    Journal of Functional Analysis, 283/10, 109634, 2022. (doi) (pdf) (reproducible)
  5. S. F., E. Tadmor, M. Zhong, On the sparsity of LASSO minimizers in sparse data recovery.
    Constructive Approximation, 57, 901--919, 2023. (doi) (pdf)
  6. S. F., C. Liao, Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?
    Constructive Approximation, 57, 489--520, 2023. (doi) (pdf) (reproducible)
  7. S. F., C. Liao, S. Shahrampour, Y. Wang, Learning from non-random data in Hilbert spaces: an optimal recovery perspective.
    Sampling Theory, Signal Processing, and Data Analysis, 20, 5, 2022. (doi) (pdf) (reproducible)
  8. M. Ettehad, S. F., Instances of computational optimal recovery: dealing with observation errors.
    SIAM/ASA Journal on Uncertainty Quantification, 9/4, 1438--1456, 2021. (doi) (pdf) (reproducible)
  9. S. F., Raconte-moi ... le Compressive Sensing.
    La Gazette des Mathématiciens, 168, 2021. (journal) (pdf)
  10. S. F., D. Needell, R. Pathak, Y. Plan, M. Wootters, Weighted matrix completion from non-random, non-uniform sampling patterns.
    IEEE Transactions on Information Theory, 67/2, 1264--1290, 2021. (doi) (arXiv)
  11. I. Daubechies, R. DeVore, S. F., B. Hanin, G. Petrova, Nonlinear approximation and (deep) ReLU networks.
    Constructive Approximation, 55, 127--172, 2022. (doi) (pdf)
  12. S. F., Instances of computational optimal recovery: refined approximability models.
    Journal of Complexity, 62, 101503, 2021. (doi) (pdf) (reproducible)
  13. S. F., Facilitating OWL norm minimizations.
    Optimization Letters, 15/1, 263--269, 2021. (doi) (pdf) (reproducible)
  14. M. Ettehad, S. F., Approximability models and optimal system identification.
    Mathematics of Control, Signals, and Systems, 32/1, 19--41, 2020. (doi) (pdf) (reproducible)
  15. S. F., Sampling schemes and recovery algorithms for functions of few coordinate variables.
    Journal of Complexity, 58, 101457, 2020. (doi) (pdf) (reproducible)
  16. S. F., R. Gribonval, L. Jacques, H. Rauhut, Jointly low-rank and bisparse recovery: questions and partial answers.
    Analysis and Applications, 18/1, 25--48, 2020. (doi) (pdf)
  17. S. F., J. B. Lasserre, Computation of Chebyshev polynomials for union of intervals.
    Computational Methods and Function Theory, 19/4, 625--641, 2019. (doi) (pdf) (reproducible)
  18. S. F., M. Hielsberg, G. Mullendore, G. Petrova, P. Wojtaszczyk, Optimal algorithms for computing average temperatures.
    Mathematics of Climate and Weather Forecasting, 5, 34--44, 2019. (doi) (pdf) (reproducible)
  19. S. F., S. Subramanian, Iterative hard thresholding for low-rank recovery from rank-one projections.
    Linear Algebra and its Applications, 572, 117--134, 2019. (doi) (pdf) (reproducible)
  20. S. F., R. Lynch, Recovering low-rank matrices from binary measurements.
    Inverse Problems and Imaging, 13/4, 703--720, 2019. (doi) (pdf) (reproducible)
  21. S. F., J. B. Lasserre, Determining projection constants of univariate polynomial spaces.
    Journal of Approximation Theory, 235, 74--91, 2018. (doi) (pdf) (reproducible)
  22. R. DeVore, S. F., G. Petrova, P. Wojtaszczyk, Computing a quantity of interest from observational data.
    Constructive Approximation, 49/3, 461--508, 2019. (doi) (pdf) (reproducible) (reproducible+supplement)
  23. S. F., J. Li, Sparse recovery from inaccurate saturated measurements.
    Acta Applicandae Mathematicae, 158/1, 49--66, 2018. (doi) (pdf) (reproducible)
  24. B. Deregowska, S. F., B. Lewandowska, L. Skrzypek, On the norms and minimal properties of de la Vallée Poussin’s type operators.
    Monatshefte für Mathematik, 185/4, 601--619, 2018. (doi) (pdf)
  25. S. F., Concave Mirsky inequality and low-rank recovery.
    SIAM Journal on Matrix Analysis and Applications, 39/1, 99–-103, 2018. (doi) (pdf)
  26. S. F., G. Lecué, An IHT algorithm for sparse recovery from subexponential measurements.
    IEEE Signal Processing Letters, 24/9, 1280--1283, 2017. (doi) (pdf)
  27. R. Baraniuk, S. F., D. Needell, Y. Plan, M. Wootters, One-bit compressive sensing of dictionary-sparse signals.
    Information and Inference, 7/1, 83--104, 2018. (doi) (pdf)
  28. R. Baraniuk, S. F., D. Needell, Y. Plan, M. Wootters, Exponential decay of reconstruction error from binary measurements of sparse signals.
    IEEE Transactions on Information Theory, 63/6, 3368--3385, 2017. (doi) (pdf) (reproducible)
  29. S. F., L. Skrzypek, On maximal relative projection constants.
    Journal of Mathematical Analysis and Applications, 447/1, 309--328, 2017. (doi) (pdf) (reproducible) (supplement)
  30. S. F., T. Needham, Sparse recovery from saturated measurements.
    Information and Inference, 6/2, 196--212, 2017. (doi) (pdf) (reproducible)
  31. S. F., V. Powers, Basc: constrained approximation by semidefinite programming.
    IMA Journal on Numerical Analysis, 37/2, 1066--1085, 2017. (doi) (pdf) (reproducible)
  32. J.-L. Bouchot, S. F., P. Hitczenko, Hard thresholding pursuit algorithms: number of iterations.
    Applied and Computational Harmonic Analysis, 41/2, 412--435, 2016. (doi) (pdf) (reproducible)
  33. S. F., Computation of minimal projections and extensions.
    Numerical Functional Analysis and Optimization, 37/2, 159--185, 2016. (doi) (pdf) (reproducible)
  34. S. F., Dictionary-sparse recovery via thresholding-based algorithms.
    Journal of Fourier Analysis and Applications, 22/1, 6--19, 2016. (doi) (pdf)
  35. S. F., M. Minner, T. Needham, Sparse disjointed recovery from noninflating measurements.
    Applied and Computational Harmonic Analysis, 39/3, 558--567, 2015. (doi) (pdf) (reproducible)
  36. D. Koslicki, S. F., G. Rosen, WGSQuikr: fast whole-genome shotgun metagenomic classification.
    PLoS ONE, 9/3, e91784, 2014. (doi) (pdf)
  37. S. F., D. Koslicki, Sparse recovery by means of nonnegative least squares.
    IEEE Signal Processing Letters, 21/4, 498--502, 2014. (doi) (pdf) (reproducible)
  38. D. Koslicki, S. F., G. Rosen, Quikr: a method for rapid reconstruction of bacterial communities via compressive sensing.
    Bioinformatics, 29/17, 2096--2102, 2013. (doi) (pdf)
  39. S. F., Stability and robustness of $\ell_1$-minimizations with Weibull matrices and redundant dictionaries.
    Linear Algebra and its Applications, 441, 4--21, 2014. (doi) (pdf)
  40. S. F., T. Sorokina, Generating dimension formulas for multivariate splines.
    Albanian Journal of Mathematics, 7/1, 24--35, 2013. (article) (pdf)
  41. S. F., Hard thresholding pursuit: an algorithm for compressive sensing.
    SIAM Journal on Numerical Analysis, 49/6, 2543--2563, 2011. (doi) (pdf)
  42. S. F., A. Pajor, H. Rauhut, T. Ullrich, The Gelfand widths of $\ell_p$-balls for $0 < p \le 1$.
    Journal of Complexity, 26/6, 629--640, 2010. (doi) (pdf)
  43. S. F., R. Gribonval, Real versus complex null space properties for sparse vector recovery.
    Comptes Rendus de l'Academie des Sciences, 348/15-16, 863--865, 2010. (doi) (pdf)
  44. S. F., A note on guaranteed sparse recovery via $\ell_1$-minimization.
    Applied and Computational Harmonic Analysis, 29/1, 97--103, 2010. (doi) (pdf)
  45. S. F., M.-J. Lai, Sparse recovery with pre-Gaussian random matrices.
    Studia Mathematica, 200, 91--102, 2010. (doi) (pdf)
  46. S. F., Allometry constants of finite-dimensional spaces: theory and computations.
    Numerische Mathematik, 112/4, 535--564, 2009. (doi) (pdf)
  47. S. F., M.-J. Lai, Sparsest solutions of underdetermined linear systems via $\ell_q$-minimization for $0 < q \le 1$.
    Applied and Computational Harmonic Analysis, 26/3, 395--407, 2009. (doi) (pdf) (reproducible)
  48. S. F., Open questions around the spline orthoprojector.
    East Journal on Approximations, 14/2, 241--253, 2008. (pdf)
  49. S. F., Yu. Kryakin, A. Shadrin, On the exact constant in Jackson-Stechkin inequality for the uniform metric.
    Constructive Approximation, 29/2, 157--179, 2009. (doi) (pdf)
  50. S. F., On the value of the max-norm of the orthogonal projector onto splines with multiple knots.
    Journal of Approximation Theory, 140/2, 154--177, 2006. (doi) (pdf)
  51. S. F., Interlacing property for B-splines.
    Journal of Approximation Theory, 135/1, 1--21, 2005. (doi) (pdf)
  52. S. F., On the best conditioned bases of quadratic polynomials.
    Journal of Approximation Theory, 130/1, 46--56, 2004. (doi) (pdf)


  1. S. F., Flavors of compressive sensing.
    Approximation Theory XV: San Antonio 2016, Springer Proceedings in Mathematics & Statistics, vol 201, 61--104. (doi) (pdf) (reproducible)

Refereed proceedings papers and book chapters

  1. S. F., Linearly embedding sparse vectors from $\ell_2$ to $\ell_1$ via deterministic dimension-reducing maps.
    Explorations in the Mathematics of Data Science, Birkhäuser, to appear. (pdf) (reproducible)
  2. S. F., C. Liao, S-procedure relaxation: a case of exactness involving Chebyshev centers.
    Explorations in the Mathematics of Data Science, Birkhäuser, to appear. (pdf)
  3. S. F., C. Liao, N. Veldt, On the optimal recovery of graph signals.
    Proceedings of SampTA 2023, New Haven. (doi) (pdf) (reproducible)
  4. S. F., D. Koslicki, Finer metagenomic reconstruction via biodiversity optimization.
    NeurIPS 2020, Vancouver (online). (pdf) (reproducible)
  5. S. F., L. Jacques, One-bit sensing of low-rank and bisparse matrices.
    Proceedings of SampTA 2019, Bordeaux. (doi) (pdf)
  6. S. F., D. Needell. Y. Plan, M. Wootters, De-biasing low-rank projection for matrix completion.
    Wavelets and Sparsity XVII, International Society for Optics and Photonics, 2017. (doi) (pdf)
  7. S. F., Complexity of multivariate problems based on binary information.
    Proceedings of SampTA 2017, Tallinn. (doi) (pdf)
  8. S. F., Stability and robustness of weak orthogonal matching pursuits.
    Recent Advances in Harmonic Analysis and Applications, Springer Proceedings in Mathematics & Statistics, vol 25, 395--405. (proceedings) (pdf)
  9. S. F., Recovering jointly sparse vectors via hard thresholding pursuit.
    Proceedings of SampTA 2011, Singapore. (proceedings) (pdf)
  10. A. Cohen, R. DeVore, S. F., H. Rauhut, Recovery of functions of many variables via compressive sensing.
    Proceedings of SampTA 2011, Singapore. (proceedings) (pdf)
  11. S. F., Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants.
    Approximation Theory XIII: San Antonio 2010, Springer Proceedings in Mathematics, vol 13, 65--77. (proceedings) (pdf)
  12. S. F., Some comments on the comparison between condition numbers and projection constants.
    Approximation Theory XII: San Antonio 2007, M. Neamtu and L. L. Schumaker (eds.), Nashboro Press, 2008, 143--156. (pdf)

Not for publication

  1. S. F., Three topics in multivariate spline theory. (pdf) (reproducible)
  2. P. Clarke, S. F., Symbolic spline computations. (pdf)
  3. F. Balabdaoui, S. F., J. Wellner, On the Hermite spline conjecture and its connection to k-monotone densities. (pdf)
  4. S. F., T. Sorokina, On the dimension of multivariate spline spaces, especially on Alfeld splits. (pdf)
  5. S. F., On definitions of discrete topological chaos and their relations on intervals. (pdf)