Random sampling of sparse trigonometric polynomials

Bass, 2004, Random sampling of multivariate trigonometric polynomials, SIAM J. Math. Anal., 36, 773, 10.1137/S0036141003432316 Boucheron, 2000, A sharp concentration inequality with applications, Random Structures Algorithms, 16, 277, 10.1002/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO;2-1 Boyd, 2004 D. Callan, On conjugates for set partitions and integer compositions, Preprint, arXiv:math.Co/0508052, 2005 Chen, 1999, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33, 10.1137/S1064827596304010 Candes, 2006, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 489, 10.1109/TIT.2005.862083 E. Candes, T. Tao, Near optimal signal recovery from random projections and universal encoding strategies, IEEE Trans. Inform. Theory (2006), in press E. Candes, J. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. (2006), in press E. Candes, J. Romberg, Practical signal recovery from random projections, Preprint, 2004 Donoho, 2006, Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289, 10.1109/TIT.2006.871582 D.L. Donoho, Y. Tsaig, Extensions of compressed sensing, EURASIP J. Appl. Signal Proc. (2006), in press Donoho, 2006, For most large underdetermined systems of linear equations the minimal ℓ1-norm solution is also the sparsest solution, Comm. Pure Appl. Math., 59, 797, 10.1002/cpa.20132 Donoho, 2005, Sparse nonnegative solutions of underdetermined linear equations, Proc. Natl. Acad. Sci. USA, 102, 9446, 10.1073/pnas.0502269102 Donoho, 2005, Neighborliness of randomly-projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA, 102, 9452, 10.1073/pnas.0502258102 A. Gilbert, J. Tropp, Signal recovery from partial information via orthogonal matching pursuit, Preprint, 2005 Knuth, 2005, Problem 11151, Amer. Math. Monthly, 112, 367, 10.2307/30037481 S. Kunis, H. Rauhut, Random sampling of sparse trigonometric polynomials II: Orthogonal matching pursuit versus basis pursuit, Preprint, 2006 Potts, 1998, Fast Fourier transforms for nonequispaced data: A tutorial, 249 Riordan, 1958 M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Notices, in press Sloane Stanley, 1997 Weisstein Wilf, 1994 Zou, 2005, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. Comput. Phys., 211, 572, 10.1016/j.jcp.2005.06.005