Roman Vershynin | Publications by Year

• R. Vershynin, Approximating the moments of marginals of high dimensional distributions, submitted.
• R. Vershynin, On the role of sparsity in Compressed Sensing and Random Matrix Theory, submitted. Commentary.
• T. Strohmer, R. Vershynin, Comments on the randomized Kaczmarz method, Journal of Fourier Analysis and Applications, DOI: 10.1007/s00041-009-9082-0. Commentary.
• R. Vershynin, Spectral norm of products of random and deterministic matrices, submitted. Commentary.
• M. Rudelson, R. Vershynin, The least singular value of a random square matrix is O(n^{-1/2}), Comptes rendus de l'Académie des sciences - Mathématique 346 (2008), 893--896. Commentary.
• M. Rudelson, R. Vershynin, The smallest singular value of a random rectangular matrix, Communications on Pure and Applied Mathematics, to appear. Commentary. Slides.
• D. Needell, R. Vershynin, Signal recovery from incomplete and inaccurate measurements via Regularized Orthogonal Matching Pursuit, IEEE Journal of Selected Topics in Signal Processing, to appear. Commentary.
  
  A conference version: D. Needell, R. Vershynin, Signal recovery from incomplete and inaccurate measurements via ROMP, SAMPTA'09 (8th international conference on Sampling Theory and Applications), 2009.
  
  Another review-style conference version: D. Needell, J. A. Tropp, and R. Vershynin, Greedy signal recovery review, Proc. 42nd Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, Oct. 2008.
  
  One more conference version: D. Needell, R. Vershynin, Greedy signal recovery and uncertainty principles, Computational Imaging VI, IS&T/SPIE 19th Annual Symposium, 2008. Proc. SPIE Vol. 6814, 68140J.
• D. Needell, R. Vershynin, Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit, Foundations of Computational Mathematics 9 (2009), 317--334. Commentary.
• M. Rudelson, R. Vershynin, The Littlewood-Offord Problem and invertibility of random matrices, Advances in Mathematics 218 (2008), 600--633. Commentary.
• R. Vershynin, Some problems in asymptotic convex geometry and random matrices motivated by numerical algorithms. Banach spaces and their applications in analysis, 209--218, Walter de Gruyter, Berlin, 2007.
• M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, Journal of the ACM (2007), Art. 21, 19 pp. Commentary.
• Yu. Lyubarskii, R. Vershynin, Uncertainty principles and vector quantization, submitted. Commentary. Slides.
• A. Gilbert, M. Strauss, J. Tropp, R. Vershynin, One sketch for all: fast algorithms for compressed sensing, STOC'07---Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 237--246, ACM, New York, 2007.
• B. Klartag, R. Vershynin, Small ball probability and Dvoretzky theorem, Israel Journal of Mathematics 157 (2007), 193--207. Commentary.
• T. Strohmer, R. Vershynin, A randomized solver for linear systems with exponential convergence, Approximation, randomization and combinatorial optimization, 499--507, Lecture Notes in Comput. Sci., 4110, Springer, Berlin, 2006. Commentary
  
  Journal version: A randomized Kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications 15 (2009), 262--278.
• R. Vershynin, Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, FOCS 2006 (47th Annual Symposium on Foundations of Computer Science), 133--142. Commentary
  
  Journal version: Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, SIAM Journal on Computing 39 (2009), 646--678 (Invited paper).
• A. Gilbert, M. Strauss, J. Tropp, R. Vershynin, Algorithmic linear dimension reduction in the ell-1 norm for sparse vectors, submitted. Commentary.
  
  Conference version: Algorithmic Linear Dimension Reduction in the L1 Norm for Sparse Vectors, Allerton 2006 (44th Annual Allerton Conference on Communication, Control, and Computing), invited paper.
• M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, CISS 2006 (40th Annual Conference on Information Sciences and Systems), invited paper. Commentary.
  
  Journal version: On sparse reconstruction from Fourier and Gaussian measurements, Communications on Pure and Applied Mathematics 61 (2008), 1025-1045. Commentary.
• R. Vershynin, Random sets of isomorphism of linear operators on Hilbert space, High dimensional probability, 148--154, IMS Lecture Notes Monogr. Ser., 51, Inst. Math. Statist., Beachwood, OH, 2006. Commentary.
• R. Vershynin, Isoperimetry of waists and local versus global asymptotic convex geometries (with an appendix by M. Rudelson and R. Vershynin), Duke Mathematical Journal 131 (2006), 1--16. Commentary.
• M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603--648. Commentary. Introductory Notes.
• M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, International Mathematical Research Notices 64 (2005), 4019--4041. Commentary.
  
  Conference version: E. Candes, M. Rudelson, T. Tao, R. Vershynin, Error correction via Linear Programming, FOCS 2005 (46th Annual Symposium on Foundations of Computer Science), 295--308.
• R. Vershynin, Frame expansions with erasures: an approach through the non-commutative operator theory, Applied and Computational Harmonic Analysis 18 (2005), 167--176 Commentary.
• R. Vershynin, Integer cells in convex sets, Advances in Mathematics 197 (2005), 248--273.
• P. G. Casazza, O. Christensen, A. M. Lindner, R. Vershynin, Frames and the Feichtinger conjecture, Proceedings of the AMS 133 (2005), 1025--1033.
• A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, R. Vershynin, Euclidean embeddings in spaces of finite volume ratio via random matrices, Journal für die Reine und Angewandte Mathematik 589 (2005), 1--19.
• A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, R. Vershynin, Random Euclidean embeddings in spaces of bounded volume ratio, Comptes Rendus de l'Académie des sciences - Mathématique 339 (2004), 33--38.
• S. Mendelson, R. Vershynin, Remarks on the geometry of coordinate projections in R^n, Israel Journal of Mathematics 140 (2004), 203--220.
• S. Mendelson, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae 152 (2003), 37--55.
• G. Schechtman, N. Tomczak-Jaegermann, R. Vershynin, Maximal l_p^n-structures in spaces with extremal parameters, Geometric aspects of functional analysis, 223--240, Lecture Notes in Mathematics, 1807, Springer, Berlin, 2003.
• M. Rudelson, R. Vershynin, Embedding Levy families into Banach spaces, Geometric and Functional Analysis 12 (2002), 183--198.
• R. Vershynin, John's decompositions: selecting a large part, Israel Journal of Mathematics 122 (2001), 253--277.
• S. Mendelson, R. Vershynin, Entropy, combinatorial dimensions and random averages. In: COLT 2002 (15th Annual Conference on Computational Learning Theory), edited by J. Kivinen and R. Sloan, Springer 2002, p. 14--28.
• N. Tomczak-Jaegermann, R. Vershynin, Sizes of projections of symmetric convex bodies, unpublished (2001).
• R. Vershynin, Subsequences of frames, Studia Mathematica 145 (2001), 185--197.
• R. Vershynin, On large random almost Euclidean bases, Acta Mathematica Universitatis Comenianae 69 (2000), no. 2, 137--144.
• R. Vershynin, Absolutely representing systems, uniform smoothness and type, Questionae Mathematica 23 (2000), 87--98.
• R. Vershynin, On constructions of strong and uniformly minimal M-bases in Banach spaces, Archiv der Mathematik (Basel) 74 (2000), 50--60.
• R. Vershynin, Embedding of operator ranges and the reflexivity of Banach spaces (Russian), Ukrainian Mathematical Journal 51 (1999), 293--296.
• R. Vershynin, On 1+epsilon_n-bounded M-bases (Russian), Russian Mathematics (Izvestiya VUZ. Matematika) 43 (1999), 22--25.
• R. Vershynin, On representing and absolutely representing systems in Banach spaces (Russian), Matematicheskaya Fizika, Analiz, Geometriya 5 (1998), 3--14.
• V. Kadets, R. Vershynin, The selection problem for bases with brackets and for strong M-bases, Rendiconti Istituto Lombardo Sez. A 131 (1997), 169--177.