Roman Vershynin | Publications by Topic

Theoretical Mathematics

Geometric Functional Analysis
Concentration of measure, sections of convex bodies, John's decompositions, geometry of Banach spaces
Operator Theory
Norms, invertibility, coordinate restrictions, approximations
Geometric Aspects of Combinatorics
Combinatorial dimension, integer points in convex sets

Applied Mathematics

Numerical Analysis
Linear programming, solvers of linear systems, Monte-Carlo methods for large matrices, low rank approximations
Computational Harmonic Analysis, Compressed Sensing and Coding
Uncertainty principles, vector quantization, signal processing, error correcting codes, sparse reconstruction, dimension reduction, frames
Statistical Learning Theory
Applications to empirical processes

Some papers are listed under multiple categories.

Geometric Functional Analysis

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.
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.
M. Rudelson, R. Vershynin, The Littlewood-Offord Problem and invertibility of random matrices, Advances in Mathematics 218 (2008), 600--633. Commentary.
B. Klartag, R. Vershynin, Small ball probability and Dvoretzky theorem, Israel Journal of Mathematics 157 (2007), 193--207. 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.
R. Vershynin, Integer cells in convex sets, Advances in Mathematics 197 (2005), 248--273.
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.
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.

Operator Theory

R. Vershynin, Approximating the moments of marginals of high dimensional distributions, submitted.
M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, Journal of the ACM (2007), Art. 21, 19 pp. 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.
M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603--648. Commentary. Introductory Notes.
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, Entropy and the combinatorial dimension, Inventiones Mathematicae 152 (2003), 37--55.

Geometric Aspects of Combinatorics

M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603--648. Commentary. Introductory Notes.
R. Vershynin, Integer cells in convex sets, Advances in Mathematics 197 (2005), 248--273.
S. Mendelson, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae 152 (2003), 37--55.
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.

Numerical Analysis

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.
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.
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).

Computational Harmonic Analysis, Compressed Sensing and Coding

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.

A 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.

Another 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.
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.
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.
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.

Statistical Learning Theory

M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603--648. Commentary. Introductory Notes.
S. Mendelson, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae 152 (2003), 37--55.
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.