The Geometry of Off-the-Grid Compressed Sensing
Tóm tắt
Compressed sensing (CS) ensures the recovery of sparse vectors from a number of randomized measurements proportional to their sparsity. The initial theory considers discretized domains, and the randomness makes the physical positions of the grid nodes irrelevant. Most imaging devices, however, operate over some continuous physical domain, and it makes sense to consider Dirac masses with arbitrary positions. In this article, we consider such a continuous setup and analyze the performance of the BLASSO algorithm, which is the continuous extension of the celebrated LASSO
$$\ell ^1$$
regularization method. This approach is appealing from a numerical perspective because it avoids to discretize the domain of interest. Previous works considered translation-invariant measurements, such as randomized Fourier coefficients, in which it makes clear that the discrete theory should be extended by imposing a minimum distance separation constraint (often called “Rayleigh limit”) between the Diracs. These prior works, however, rule out many domains and sensing operators of interest, which are not translation invariant. This includes, for instance, Laplace measurements over the positive reals and Gaussian mixture models over the mean-covariance space. Our theoretical advances crucially rely on the introduction of a canonical metric associated with the measurement operator, which is the so-called Fisher geodesic distance. In the case of Fourier measurements, one recovers the Euclidean metric, but this metric can cope with arbitrary (possibly non-translation invariant) domains. Furthermore, it is naturally invariant under joint reparameterization of both the sensing operator and the Dirac locations. Our second and main contribution shows that if the Fisher distance between spikes is larger than a Rayleigh separation constant, then the BLASSO recovers in a stable way a stream of Diracs, provided that the number of measurements is proportional (up to log factors) to the number of Diracs. We measure the stability using an optimal transport distance constructed on top of the Fisher geodesic distance. Our result is (up to log factor) sharp and does not require any randomness assumption on the amplitudes of the underlying measure. Our proof technique relies on an infinite-dimensional extension of the so-called golfing scheme which operates over the space of measures and is of general interest.
Tài liệu tham khảo
Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds (2014). https://doi.org/10.1515/9781400830244
Akkouchi, M.: On the convolution of exponential distributions. Journal of the Chungcheong Mathematical Society 21(4), 501–510 (2008)
Amari, S.i., Nagaoka, H.: Methods of information geometry, vol. 191. American Mathematical Soc. (2007)
Azais, J.M., De Castro, Y., Gamboa, F.: Spike detection from inaccurate samplings. Applied and Computational Harmonic Analysis 38(2), 177–195 (2015)
Bach, F.: Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research 18(19), 1–53 (2017)
Bendory, T., Eldar, Y.C.: Recovery of sparse positive signals on the sphere from low resolution measurements. IEEE Signal Processing Letters 22(12), 2383–2386 (2015)
Beurling, A.: Sur les intégrales de fourier absolument convergentes et leur application à une transformation fonctionelle. In: Ninth Scandinavian Mathematical Congress, pp. 345–366 (1938)
Boyd, N., Schiebinger, G., Recht, B.: The alternating descent conditional gradient method for sparse inverse problems. SIAM Journal on Optimization 27(2), 616–639 (2017)
Bredies, K., Pikkarainen, H.K.: Inverse problems in spaces of measures. ESAIM Control, Optimisation and Calculus of Variations 19(1), 190–218 (2013)
Burger, M., Osher, S.: Convergence rates of convex variational regularization. Inverse problems 20(5), 1411 (2004)
Burges, C.J.: Geometry and invariance in kernel based methods. MIT Press (1999)
Caffarelli, L., McCann, R.J.: Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics 171(2), 673–730 (2010)
Campbell, L.L.: An extended čencov characterization of the information metric. Proceedings of the American Mathematical Society 98(1), 135–141 (1986)
Candès, E.J., Fernandez-Granda, C.: Super-resolution from noisy data. Journal of Fourier Analysis and Applications 19(6), 1229–1254 (2013). https://doi.org/10.1007/s00041-013-9292-3
Candès, E.J., Fernandez-Granda, C.: Towards a mathematical theory of super-resolution. Communications on Pure and Applied Mathematics 67(6), 906–956 (2014). https://doi.org/10.1002/cpa.21455
Candes, E.J., Plan, Y.: A probabilistic and RIPless theory of compressed sensing. IEEE Transactions on Information Theory 57(11), 7235–7254 (2011)
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory 52(2), 489–509 (2006)
Cencov, N.N.: Statistical decision rules and optimal inference. 53. American Mathematical Soc. (1982)
Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM review 43(1), 129–159 (2001)
Chizat, L., Bach, F.: On the global convergence of gradient descent for over-parameterized models using optimal transport. In: Advances in neural information processing systems, pp. 3036–3046 (2018)
Chizat, L., Peyré, G., Schmitzer, B., Vialard, F.X.: Unbalanced optimal transport: Dynamic and kantorovich formulations. Journal of Functional Analysis 274(11), 3090–3123 (2018)
Cormode, G., Garofalakis, M., Haas, P.J., Jermaine, C.: Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches. Foundations and Trends in Databases 4, 1–294 (2011). https://doi.org/10.1561/1900000004
Costa, S.I., Santos, S.A., Strapasson, J.E.: Fisher information distance: a geometrical reading. Discrete Applied Mathematics 197, 59–69 (2015)
Dasgupta, S., Gupta, A.: An Elementary Proof of a Theorem of Johnson and Lindenstrauss. Random Structures and Algorithms 22(1), 60–65 (2003). https://doi.org/10.1002/rsa.10073
De Castro, Y., Gamboa, F.: Exact reconstruction using Beurling minimal extrapolation. Journal of Mathematical Analysis and applications 395(1), 336–354 (2012)
De Castro, Y., Gamboa, F., Henrion, D., Lasserre, J.B.: Exact solutions to super resolution on semi-algebraic domains in higher dimensions. IEEE Transactions on Information Theory 63(1), 621–630 (2016)
Denoyelle, Q., Duval, V., Peyré, G.: Support recovery for sparse super-resolution of positive measures. Journal of Fourier Analysis and Applications 23(5), 1153–1194 (2017)
Denoyelle, Q., Duval, V., Peyre, G., Soubies, E.: The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy. Inverse Problems (2019). https://doi.org/10.1088/1361-6420/ab2a29
Donoho, D.L.: Compressed sensing. IEEE Transactions on information theory 52(4), 1289–1306 (2006)
Duval, V., Peyré, G.: Exact support recovery for sparse spikes deconvolution. Foundations of Computational Mathematics 15(5), 1315–1355 (2015)
Duval, V., Peyré, G.: Sparse spikes super-resolution on thin grids I: the LASSO. Inverse Problems 33(5), 055008 (2017). https://doi.org/10.1088/1361-6420/aa5e12
Eftekhari, A., Tanner, J., Thompson, A., Toader, B., Tyagi, H.: Sparse non-negative super-resolution-simplified and stabilised. arXiv preprint arXiv:1804.01490 (2018)
Ekanadham, C., Tranchina, D., Simoncelli, E.P.: A unified framework and method for automatic neural spike identification. Journal of neuroscience methods 222, 47–55 (2014)
Facchi, P., Kulkarni, R., Man’ko, V.I., Marmo, G., Sudarshan, E.C., Ventriglia, F.: Classical and quantum Fisher information in the geometrical formulation of quantum mechanics. Physics Letters, Section A: General, Atomic and Solid State Physics 374(48), 4801–4803 (2010). https://doi.org/10.1016/j.physleta.2010.10.005
Fernandez-Granda, C.: Support detection in super-resolution. Proc. Proceedings of the 10th International Conference on Sampling Theory and Applications pp. 145–148 (2013)
Foucart, S., Rauhut, H.: A mathematical introduction to compressive sensing, vol. 1. Birkhäuser Basel (2013)
Gribonval, R., Blanchard, G., Keriven, N., Traonmilin, Y.: Compressive statistical learning with random feature moments. arXiv preprint arXiv:1706.07180 (2017)
Griffiths, D.: Introduction to Quantum Mechanics. Pearson Education, Inc. (2004). https://doi.org/10.1063/1.2958160
Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory 57(3), 1548–1566 (2011)
Kunis, S., Peter, T., Römer, T., von der Ohe, U.: A multivariate generalization of Prony’s method. Linear Algebra and its Applications 490, 31–47 (2016)
Liao, W., Fannjiang, A.: MUSIC for single-snapshot spectral estimation: Stability and super-resolution. Applied and Computational Harmonic Analysis 40(1), 33–67 (2016)
Liero, M., Mielke, A., Savaré, G.: Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures. Inventiones mathematicae 211(3), 969–1117 (2018)
Minsker, S.: On some extensions of bernstein’s inequality for self-adjoint operators. Statistics & Probability Letters 127, 111–119 (2017)
Poon, C., Keriven, N., Peyré, G.: Support localization and the fisher metric for off-the-grid sparse regularization. In: Proc. AISTATS’19 (2019). arXiv:1810.03340
Poon, C., Peyré, G.: Multi-dimensional sparse super-resolution. SIAM Journal on Mathematical Analysis 51(1), 1–44 (2019). https://doi.org/10.1137/17M1147822
Prony, G.: Essai expérimental et analytique: sur les lois de la dilatabilité de fluides élastique et sur celles de la force expansive de la vapeur de l’alkool, à différentes températures. J. de l’Ecole Polytechnique 1(22), 24–76 (1795)
Rao, C.R.: Information and the accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc. 37, 81–91 (1945)
Roy, R., Kailath, T.: ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on acoustics, speech, and signal processing 37(7), 984–995 (1989)
Santambrogio, F.: Optimal transport for applied mathematicians. Birkäuser, NY 55, 58–63 (2015)
Sauer, T.: Prony’s method in several variables. Numerische Mathematik 136(2), 411–438 (2017)
Schiebinger, G., Robeva, E., Recht, B.: Superresolution without separation. Information and Inference: A Journal of the IMA 7(1), 1–30 (2018)
Schmidt, R.: Multiple emitter location and signal parameter estimation. IEEE transactions on antennas and propagation 34(3), 276–280 (1986)
Soubies, E., Blanc-Féraud, L., Aubert, G.: A continuous exact \(\ell _0\) penalty (CEL0) for least squares regularized problem. SIAM Journal on Imaging Sciences 8(3), 1607–1639 (2015)
Tang, G., Bhaskar, B.N., Recht, B.: Sparse recovery over continuous dictionaries-just discretize. In: 2013 Asilomar Conference on Signals, Systems and Computers, pp. 1043–1047. IEEE (2013)
Tang, G., Bhaskar, B.N., Shah, P., Recht, B.: Compressed sensing off the grid. IEEE transactions on information theory 59(11), 7465–7490 (2013)
Tibshirani, R.: Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B (Methodological) pp. 267–288 (1996)
Tropp, J.A.: Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information theory 50(10), 2231–2242 (2004)