Roman Vershynin | Publications

Research Publications

Y. He, R. Vershynin, Y. Zhu, Online differentially private synthetic data generation, submitted. arXiv
A. Ferber, J. Han, D. Mao, R. Vershynin, Hamiltonicity of sparse pseudorandom graphs, submitted. arXiv
G. Kumar, T. Strohmer, R. Vershynin, PrivStream: an algorithm for streaming differentially private data, submitted. arXiv
R. Vershynin, Are most Boolean functions determined by low frequencies? submitted. arXiv
P. Ivanisvili, O. Klein, R. Vershynin, Covering the hypercube, the uncertainty principle, and an interpolation formula, submitted. arXiv
Y. He, T. Strohmer, R. Vershynin, Y. Zhu, Differentially private low-dimensional representation of high-dimensional data, submitted. arXiv
Y. He, R. Vershynin, Y. Zhu, Algorithmically effective differentially private synthetic data, COLT 2023. arXiv
M. Boedihardjo, T. Strohmer, R. Vershynin, Covariance loss, Szemeredi regularity, and differential privacy, submitted. arXiv
K. Dover, Z. Cang, A. Ma, Q. Nie, R. Vershynin, AVIDA: alternating method for visualizing and integrating data, Journal of Computational Science 68 (2023), Article 101998. arXiv
M. Boedihardjo, T. Strohmer, R. Vershynin, Private measures, random walks, and synthetic data, Probability Theory and Related Fields, to appear. arXiv
P. Baldi, R. Vershynin, The quarks of attention: structure and capacity of neural attention building blocks, Artificial Intelligence 319 (2023), Article 103901. arXiv
Y. S. Tan, R. Vershynin, Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval, Journal of Machine Learning Research 24 (2023), 1--47. arXiv
M. Boedihardjo, T. Strohmer, R. Vershynin, Privacy of synthetic data: a statistical framework, IEEE Transactions on Information Theory 69 (2023), 520--527. arXiv
M. Boedihardjo, T. Strohmer, R. Vershynin, Private sampling: a noiseless approach for generating differentially private synthetic data, SIAM Journal on Mathematics of Data Science 4 (2022), 1082--1115. arXiv
P. Baldi, R. Vershynin, Foundations of attention mechanisms in deep neural network architectures, NeurIPS 2022.
M. Boedihardjo, T. Strohmer, R. Vershynin, Covariance's loss is privacy's gain: computationally efficient, private and accurate synthetic data, Foundations of Computational Mathematics, 2022, 1--48. arXiv
J. Bryson, R. Vershynin, H. Zhao, Marchenko-Pastur law with relaxed independence conditions, Random Matrices: Theory and Applications, Volume 10 (2021), Article 2150040. arXiv

P. Baldi, R. Vershynin, A theory of capacity and sparse neural encoding, Neural Networks 143 (2021), 12--27. arXiv
G. Livshyts, K. Tikhomirov, R. Vershynin, The smallest singular value of inhomogeneous square random matrices, Annals of Probability 49 (2021), 1286--1309. arXiv
R. Vershynin, Memory capacity of neural networks with threshold and rectified linear unit activations, SIAM Journal on Mathematics of Data Science 2 (2020), 1004--1033. arXiv
R. Vershynin, Concentration inequalities for random tensors, Bernoulli 26 (2020), 3139--3162. arXiv
P. Baldi, R. Vershynin, Polynomial threshold functions, hyperplane arrangements, and random tensors, SIAM Journal on Mathematics of Data Science 1 (2019), 699--729. arXiv
P. Baldi, R. Vershynin, The capacity of feedforward neural networks, Neural Networks 116 (2019), 288--311. arXiv Featured in ZDNet News.
Y. S. Tan, R. Vershynin, Phase retrieval via randomized Kaczmarz: theoretical guarantees, Information and Inference 8 (2019), 97--123. arXiv
P. Baldi, R. Vershynin, On neuronal capacity, Journal of Statistical Mechanics: Theory and Experiment (2019) 124012, 14 pp. (invited paper). Conference version: Neuronal capacity, Advances in Neural Information Processing Systems 31 (NIPS 2018), 7729--7738.
Y. S. Tan, R. Vershynin, Polynomial time and sample complexity for non-Gaussian component analysis: spectral methods, Proceedings of the 31st Conference On Learning Theory (COLT 2018), PMLR 75 (2018), 498--534. arXiv
E. Rebrova, R. Vershynin, Norms of random matrices: local and global problems, Advances in Mathematics 324 (2018), 40--83. arXiv
J. Banks, C. Moore, R. Vershynin, J. Xu, Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization, IEEE Transactions on Information Theory 64 (2018), 4872--4994. arXiv Conference version: 2017 IEEE International Symposium on Information Theory (ISIT).
C. Liaw, A. Mehrabian, Y. Plan, R. Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets, Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014--2016, B. Klartag, E. Milman (eds.), Lecture Notes in Mathematics 2169, Springer, 2017, pp. 277--299. arXiv
C. Le, E. Levina, R. Vershynin, Concentration and regularization of random graphs, Random Structures and Algorithms 51 (2017), 538--561. arXiv
M. Rudelson, R. Vershynin, No-gaps delocalization for general random matrices, Geometric and Functional Analysis 26 (2016), 1716--1776. arXiv
Y. Plan, R. Vershynin, The generalized Lasso with non-linear observations, IEEE Transactions on Information Theory 62 (2016), 1528--1537. arXiv
C. Le, E. Levina, R. Vershynin, Sparse random graphs: regularization and concentration of the Laplacian, unpublished. This manuscript is superseded by our newer paper. arXiv
O. Guedon, R. Vershynin, Community detection in sparse networks via Grothendieck's inequality, Probability Theory and Related Fields 165 (2016), 1025--1049. arXiv
C. Le, E. Levina, R. Vershynin, Optimization via low-rank approximation, with applications to community detection in networks, Annals of Statistics 44 (2016), 373--400. arXiv , supplement.
B. Farrell, R. Vershynin, Smoothed analysis of symmetric random matrices with continuous distributions, Proceedings of the AMS 144 (2016), 2257--2261. arXiv .
Hagelstein's weak triangle inequality for weak L1 norm used in this paper is discussed here:
R. Vershynin, Weak triangle inequalities for weak L1 norm, unpublished.
R. Giryes, Y. Plan, R. Vershynin, On the effective measure of dimension in analysis cosparse model, IEEE Transactions on Information Theory 61 (2015), 5745--5753. arXiv
Conference version:
On the effective measure of dimension in total variation minimization, Sampling Theory and Applications (SampTA), 2015, IEEE, 593--597.
Y. Plan, R. Vershynin, E. Yudovina, High-dimensional estimation with geometric constraints, Information and Inference 0 (2016), 1--40. arXiv
M. Rudelson, R. Vershynin, Small ball probabilities for linear images of high dimensional distributions, International Mathematics Research Notices 19 (2015), 9594--9617. arXiv
M. Rudelson, R. Vershynin, Delocalization of eigenvectors of random matrices with independent entries, Duke Mathematical Journal 164 (2015), 2507--2538. arXiv
A. Ai, A. Lapanowski, Y. Plan and R. Vershynin, One-bit compressed sensing with non-Gaussian measurements, Linear Algebra and Applications 441 (2014), 222--239. arXiv
M. Rudelson, R. Vershynin, Invertibility of random matrices: unitary and orthogonal perturbations, Journal of the AMS 27 (2014), 293--338. arXiv
Y. Plan, R. Vershynin, Dimension reduction by random hyperplane tessellations, Discrete and Computational Geometry 51 (2014), 438--461. arXiv
R. Vershynin, Invertibility of symmetric random matrices, Random Structures and Algorithms 44 (2014), 135--182. arXiv
M. Rudelson, R. Vershynin, Hanson-Wright inequality and sub-gaussian concentration, Electronic Communications in Probability 18 (2013), 1-9. arXiv
Y. Plan, R. Vershynin, Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach, IEEE Transactions on Information Theory 59 (2013), 482--494. arXiv
Y. Plan, R. Vershynin, One-bit compressed sensing by linear programming, Communications on Pure and Applied Mathematics 66 (2013), 1275--1297. arXiv
N. Srivastava, R. Vershynin, Covariance estimation for distributions with 2+epsilon moments, Annals of Probability 41 (2013), 3081--3111.
R. Vershynin, A tribute to Nigel J. Kalton (1946-2010), Peter Casazza (coordinating editor), Alexander Pelczynski, Joe Diestel, Roman Vershynin, Gilles Godefroy, Notices of the AMS 59 (7), August 2012, 942--951.
E. Levina, R. Vershynin, Partial estimation of covariance matrices, Probability Theory and Related Fields 153 (2012), 405--419. arXiv
R. Vershynin, How close is the sample covariance matrix to the actual covariance matrix? Journal of Theoretical Probability 25 (2012), 655--686. arXiv
R. Vershynin, A simple decoupling inequality in probability theory, not intended for publication (2011).
R. Vershynin, Approximating the moments of marginals of high dimensional distributions, Annals of Probability 39 (2011), 1591--1606.
R. Vershynin, Spectral norm of products of random and deterministic matrices, Probability Theory and Related Fields 150 (2011), 471--509.
Yu. Lyubarskii, R. Vershynin, Uncertainty principles and vector quantization, IEEE Transactions on Information Theory 56 (2010), 3491--3501.
T. Strohmer, R. Vershynin, Comments on the randomized Kaczmarz method, Journal of Fourier Analysis and Applications 15 (2009), 437--440.
M. Rudelson, R. Vershynin, Smallest singular value of a random rectangular matrix, Communications on Pure and Applied Mathematics 62 (2009), 1707--1739.
D. Needell, R. Vershynin, Signal recovery from incomplete and inaccurate measurements via Regularized Orthogonal Matching Pursuit, IEEE Journal of Selected Topics in Signal Processing 4 (2010), 310--316.
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 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.
R. Vershynin, A note on sums of independent random matrices after Ahlswede-Winter, not intended for publication, 2009.
R. Vershynin, Golden-Thompson inequality, not intended for publication, 2009.
D. Needell, R. Vershynin, Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit, Foundations of Computational Mathematics 9 (2009), 317--334.
M. Rudelson, R. Vershynin, The least singular value of a random square matrix is O(n^{-1/2}), Comptes rendus de l'Academie des sciences - Mathematique 346 (2008), 893--896.
M. Rudelson, R. Vershynin, The Littlewood-Offord Problem and invertibility of random matrices, Advances in Mathematics 218 (2008), 600--633.
M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, Journal of the ACM (2007), Art. 21, 19 pp.
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.
T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications 15 (2009), 262--278.
Conference version: 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.
R. Vershynin, Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, SIAM Journal on Computing 39 (2009), 646--678 (Invited paper).
Conference version: 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.
A. Gilbert, M. Strauss, J. Tropp, R. Vershynin, Algorithmic linear dimension reduction in the ell-1 norm for sparse vectors, Allerton 2006 (44th Annual Allerton Conference on Communication, Control, and Computing), invited paper.
M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Communications on Pure and Applied Mathematics 61 (2008), 1025-1045.
Conference version: M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, CISS'06 (40th Annual Conference on Information Sciences and Systems), 2006, 207--212.
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.
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.
M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603--648.
M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, International Mathematical Research Notices 64 (2005), 4019--4041.
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), 668--681.
R. Vershynin, Frame expansions with erasures: an approach through the non-commutative operator theory, Applied and Computational Harmonic Analysis 18 (2005), 167--176
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, Imbedding of the images of operators and 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.

Expository Publications

Research Publications