zbMATH — the first resource for mathematics

Random sampling of sparse trigonometric polynomials. (English) Zbl 1123.94004
Summary: We study the problem of reconstructing a multivariate trigonometric polynomial having only few non-zero coefficients from few random samples. Inspired by recent work of E. J. Candès, J. K. Romberg and T. Tao [Commun. Pure Appl. Math. 59, No. 8, 1207–1223 (2006; Zbl 1098.94009)] we propose to recover the polynomial by Basis Pursuit, i.e., by \(\ell ^{1}\)-minimization. In contrast to their work, where the sampling points are restricted to a grid, we model the random sampling points by a continuous uniform distribution on the cube, i.e., we allow them to have arbitrary position. Numerical experiments show that with high probability the trigonometric polynomial can be recovered exactly provided the number \(N\) of samples is high enough compared to the “sparsity” – the number of non-vanishing coefficients. However, \(N\) can be chosen small compared to the assumed maximal degree of the trigonometric polynomial. We present two theorems that explain this observation. One of them provides the analogue of the result of Candès, Romberg and Tao. The other one is a result toward an average case analysis and, unexpectedly connects to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before. Although our proofs follow ideas of Candès et al. they are simpler.

94A20 Sampling theory in information and communication theory
42A05 Trigonometric polynomials, inequalities, extremal problems
15B52 Random matrices (algebraic aspects)
Full Text: DOI arXiv
[1] Bass, R.F.; Gröchenig, K., Random sampling of multivariate trigonometric polynomials, SIAM J. math. anal., 36, 3, 773-795, (2004) · Zbl 1096.94008
[2] Boucheron, S.; Lugosi, G.; Massart, P., A sharp concentration inequality with applications, Random structures algorithms, 16, 277-292, (2000) · Zbl 0954.60008
[3] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge Univ. Press Cambridge · Zbl 1058.90049
[4] D. Callan, On conjugates for set partitions and integer compositions, Preprint, arXiv:math.Co/0508052, 2005
[5] Chen, S.S.; Donoho, D.L.; Saunders, M.A., Atomic decomposition by basis pursuit, SIAM J. sci. comput., 20, 1, 33-61, (1999) · Zbl 0919.94002
[6] Candes, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE trans. inform. theory, 52, 2, 489-509, (2006) · Zbl 1231.94017
[7] E. Candes, T. Tao, Near optimal signal recovery from random projections and universal encoding strategies, IEEE Trans. Inform. Theory (2006), in press · Zbl 1309.94033
[8] E. Candes, J. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. (2006), in press · Zbl 1098.94009
[9] E. Candes, J. Romberg, Practical signal recovery from random projections, Preprint, 2004
[10] Donoho, D.L., Compressed sensing, IEEE trans. inform. theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016
[11] D.L. Donoho, Y. Tsaig, Extensions of compressed sensing, EURASIP J. Appl. Signal Proc. (2006), in press · Zbl 1163.94399
[12] Donoho, D.L., For most large underdetermined systems of linear equations the minimal \(\ell^1\)-norm solution is also the sparsest solution, Comm. pure appl. math., 59, 6, 797-892, (2006) · Zbl 1113.15004
[13] Donoho, D.L.; Tanner, J., Sparse nonnegative solutions of underdetermined linear equations, Proc. natl. acad. sci. USA, 102, 27, 9446-9451, (2005) · Zbl 1135.90368
[14] Donoho, D.L.; Tanner, J., Neighborliness of randomly-projected simplices in high dimensions, Proc. natl. acad. sci. USA, 102, 27, 9452-9457, (2005) · Zbl 1135.60300
[15] A. Gilbert, J. Tropp, Signal recovery from partial information via orthogonal matching pursuit, Preprint, 2005
[16] Knuth, D., Problem 11151, Amer. math. monthly, 112, 367, (2005)
[17] S. Kunis, H. Rauhut, Random sampling of sparse trigonometric polynomials II: Orthogonal matching pursuit versus basis pursuit, Preprint, 2006 · Zbl 1165.94314
[18] Potts, D.; Steidl, G.; Tasche, M., Fast Fourier transforms for nonequispaced data: A tutorial, (), 249-274, Chap. 12
[19] Riordan, J., Combinatorial analysis, (1958), Wiley
[20] M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Notices, in press · Zbl 1103.94014
[21] Sloane, N.J.A., On-line encyclopedia of integer sequences, published electronically at: · Zbl 1044.11108
[22] Stanley, R.P., Enumerative combinatorics, (1997), Cambridge Univ. Press Cambridge · Zbl 0889.05001
[23] Weisstein, E.W., Binomial sums, from MathWorld—A Wolfram web resource
[24] Wilf, H., Generating functionology, (1994), Academic Press Boston
[25] Zou, J.; Gilbert, A.; Strauss, M.; Daubechies, I., Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. comput. phys., 211, 572-595, (2005) · Zbl 1085.65128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.