×

Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. (English) Zbl 1250.60023

Summary: Consider a random sum \(\eta_1v_1 + \dots + \eta_nv_n\), where \(\eta 1,\dots,\eta n\) are independently and identically distributed (i.i.d.) random signs and \(v_1,\dots,v_n\) are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as \(\mathbf P(\eta_1v_1 + \dots + \eta_nv_n = 0)\) subject to various hypotheses on \(v_1,\dots,v_n\). In this paper we develop an inverse Littlewood-Offord theory (somewhat in the spirit of Freiman’s inverse theory in additive combinatorics), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the \(v_1,\dots,v_n\) are efficiently contained in a generalized arithmetic progression. As an application we give a new bound on the magnitude of the least singular value of a random Bernoulli matrix, which in turn provides upper tail estimates on the condition number.

MSC:

60G50 Sums of independent random variables; random walks
15B52 Random matrices (algebraic aspects)
60E15 Inequalities; stochastic orderings
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI arXiv Link