Source author record

Nikhil Srivastava

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.FA math.NA Numerical Analysis math.CO Data Structures and Algorithms math.SP math.OA Computational Complexity math-ph math.MP math.ST Statistics Theory

Catalog footprint

Research overview

14works

13topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

We develop a framework for proving rapid convergence of shifted QR algorithms which use Ritz values as shifts, in finite arithmetic. Our key contribution is a dichotomy result which addresses the known forward-instability issues surrounding the shifted QR iteration [Parlett and Le 1993]: we give a procedure which provably either computes a set of approximate Ritz values of a Hessenberg matrix with good forward stability properties, or leads to early decoupling of the matrix via a small number of QR steps. Using this framework, we show that the shifting strategy introduced in Part I of this series [Banks, Garza-Vargas, and Srivastava 2021] converges rapidly in finite arithmetic with a polylogarithmic bound on the number of bits of precision required, when invoked on matrices of controlled eigenvector condition number and minimum eigenvalue gap.

preprint2022arXiv

Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration

We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix $M\in\mathbb{C}^{n\times n}$ up to backward error $δ\|M\|$ in $O(n^4+n^3\log^2(n/δ)+\log(n/δ)^2\log\log(n/δ))$ floating point operations using $O(\log^2(n/δ))$ bits of precision. While the $O(n^4)$ complexity is prohibitive for large matrices, the algorithm is simple and may be useful for provably computing the eigenvalues of small matrices using controlled precision, in particular for computing Ritz values in shifted QR algorithms as in (Banks, Garza-Vargas, Srivastava, 2022).

preprint2022arXiv

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $δ>0$ , computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le δ$ using $O(T_{MM}(n)\log^2(n/δ))$ arithmetic operations, in finite arithmetic with $O(\log^4(n/δ)\log n)$ bits of precision. Here $T_{MM}(n)$ is the number of arithmetic operations required to multiply two $n\times n$ complex matrices numerically stably, known to satisfy $T_{MM}(n)=O(n^{ω+η})$ for every $η>0$ where $ω$ is the exponent of matrix multiplication (Demmel et al., Numer. Math., 2007). Our result significantly improves the previously best known provable running times of $O(n^{10}/δ^2)$ arithmetic operations for diagonalization of general matrices (Armentano et al., J. Eur. Math. Soc., 2018), and (with regards to the dependence on $n$ ) $O(n^3)$ arithmetic operations for Hermitian matrices (Dekker and Traub, Lin. Alg. Appl., 1971). It is the first algorithm to achieve nearly matrix multiplication time for diagonalization in any model of computation (real arithmetic, rational arithmetic, or finite arithmetic), thereby matching the complexity of other dense linear algebra operations such as inversion and $QR$ factorization up to polylogarithmic factors. The proof rests on two new ingredients. (1) We show that adding a small complex Gaussian perturbation to any matrix splits its pseudospectrum into $n$ small well-separated components. In particular, this implies that the eigenvalues of the perturbed matrix have a large minimum gap, a property of independent interest in random matrix theory. (2) We give a rigorous analysis of Roberts' Newton iteration method (Roberts, Int. J. Control, 1980) for computing the sign function of a matrix in finite arithmetic, itself an open problem in numerical analysis since at least 1986.

preprint2020arXiv

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

A matrix $A\in\mathbb{C}^{n\times n}$ is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every $A\in \mathbb{C}^{n\times n}$ is the limit of diagonalizable matrices. We prove a quantitative version of this fact conjectured by E.B. Davies: for each $δ\in (0,1)$ , every matrix $A\in \mathbb{C}^{n\times n}$ is at least $δ\|A\|$ -close to one whose eigenvectors have condition number at worst $c_n/δ$ , for some constants $c_n$ dependent only on $n$ . Our proof uses tools from random matrix theory to show that the pseudospectrum of $A$ can be regularized with the addition of a complex Gaussian perturbation. Along the way, we explain how a variant of a theorem of Śniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.

preprint2020arXiv

On Concentration Inequalities for Random Matrix Products

Consider $n$ complex random matrices $X_1,\ldots,X_n$ of size $d\times d$ sampled i.i.d. from a distribution with mean $E[X]=μ$ . While the concentration of averages of these matrices is well-studied, the concentration of other functions of such matrices is less clear. One function which arises in the context of stochastic iterative algorithms, like Oja's algorithm for Principal Component Analysis, is the normalized matrix product defined as $\prod\limits_{i=1}^{n}\left(I + \frac{X_i}{n}\right).$ Concentration properties of this normalized matrix product were recently studied by \cite{HW19}. However, their result is suboptimal in terms of the dependence on the dimension of the matrices as well as the number of samples. In this paper, we present a stronger concentration result for such matrix products which is optimal in $n$ and $d$ up to constant factors. Our proof is based on considering a matrix Doob martingale, controlling the quadratic variation of that martingale, and applying the Matrix Freedman inequality of Tropp \cite{TroppIntro15}.

preprint2020arXiv

Overlaps, Eigenvalue Gaps, and Pseudospectrum under real Ginibre and Absolutely Continuous Perturbations

Let $G_n$ be an $n \times n$ matrix with real i.i.d. $N(0,1/n)$ entries, let $A$ be a real $n \times n$ matrix with $\Vert A \Vert \le 1$ , and let $γ\in (0,1)$ . We show that with probability $0.99$ , $A + γG_n$ has all of its eigenvalue condition numbers bounded by $O\left(n^{5/2}/γ^{3/2}\right)$ and eigenvector condition number bounded by $O\left(n^3 /γ^{3/2}\right)$ . Furthermore, we show that for any $s > 0$ , the probability that $A + γG_n$ has two eigenvalues within distance at most $s$ of each other is $O\left(n^4 s^{1/3}/γ^{5/2}\right).$ In fact, we show the above statements hold in the more general setting of non-Gaussian perturbations with real, independent, absolutely continuous entries with a finite moment assumption and appropriate normalization. This extends the previous work [Banks et al. 2019] which proved an eigenvector condition number bound of $O\left(n^{3/2} / γ\right)$ for the simpler case of {\em complex} i.i.d. Gaussian matrix perturbations. The case of real perturbations introduces several challenges stemming from the weaker anticoncentration properties of real vs. complex random variables. A key ingredient in our proof is new lower tail bounds on the small singular values of the complex shifts $z-(A+γG_n)$ which recover the tail behavior of the complex Ginibre ensemble when $\Im z\neq 0$ . This yields sharp control on the area of the pseudospectrum $Λ_ε(A+γG_n)$ in terms of the pseudospectral parameter $ε>0$ , which is sufficient to bound the overlaps and eigenvector condition number via a limiting argument.

preprint2020arXiv

Scalar Poincaré Implies Matrix Poincaré

We prove that every reversible Markov semigroup which satisfies a Poincaré inequality satisfies a matrix-valued Poincaré inequality for Hermitian $d\times d$ matrix valued functions, with the same Poincaré constant. This generalizes recent results [Aoun et al. 2019, Kathuria 2019] establishing such inequalities for specific semigroups and consequently yields new matrix concentration inequalities. The short proof follows from the spectral theory of Markov semigroup generators.

preprint2016arXiv

Real Stability Testing

We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.

preprint2015arXiv

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions we recently introduced.

preprint2014arXiv

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by sqrt{c-1}+sqrt{d-1}, for all c, d \geq 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".

preprint2014arXiv

Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem

We use the method of interlacing families of polynomials introduced to prove two theorems known to imply a positive solution to the Kadison--Singer problem. The first is Weaver's conjecture $KS_{2}$ \cite{weaver}, which is known to imply Kadison--Singer via a projection paving conjecture of Akemann and Anderson. The second is a formulation due to Casazza, et al., of Anderson's original paving conjecture(s), for which we are able to compute explicit paving bounds. The proof involves an analysis of the largest roots of a family of polynomials that we call the "mixed characteristic polynomials" of a collection of matrices.

preprint2014arXiv

Ramanujan Graphs and the Solution of the Kadison-Singer Problem

We survey the techniques used in our recent resolution of the Kadison-Singer problem and proof of existence of Ramanujan Graphs of every degree: mixed characteristic polynomials and the method of interlacing families of polynomials. To demonstrate the method of interlacing families of polynomials, we give a simple proof of Bourgain and Tzafriri's restricted invertibility principle in the isotropic case.

preprint2013arXiv

Covariance estimation for distributions with $2+\varepsilon$ moments

We study the minimal sample size N=N(n) that suffices to estimate the covariance matrix of an n-dimensional distribution by the sample covariance matrix in the operator norm, with an arbitrary fixed accuracy. We establish the optimal bound N=O(n) for every distribution whose k-dimensional marginals have uniformly bounded $2+\varepsilon$ moments outside the sphere of radius $O(\sqrt{k})$ . In the specific case of log-concave distributions, this result provides an alternative approach to the Kannan-Lovasz-Simonovits problem, which was recently solved by Adamczak et al. [J. Amer. Math. Soc. 23 (2010) 535-561]. Moreover, a lower estimate on the covariance matrix holds under a weaker assumption - uniformly bounded $2+\varepsilon$ moments of one-dimensional marginals. Our argument consists of randomizing the spectral sparsifier, a deterministic tool developed recently by Batson, Spielman and Srivastava [SIAM J. Comput. 41 (2012) 1704-1721]. The new randomized method allows one to control the spectral edges of the sample covariance matrix via the Stieltjes transform evaluated at carefully chosen random points.

preprint2010arXiv

An Elementary Proof of the Restricted Invertibility Theorem

We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nikhil Srivastava

Research overview

Is this your work?

14 publications

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

On Concentration Inequalities for Random Matrix Products

Overlaps, Eigenvalue Gaps, and Pseudospectrum under real Ginibre and Absolutely Continuous Perturbations

Scalar Poincaré Implies Matrix Poincaré

Real Stability Testing

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem

Ramanujan Graphs and the Solution of the Kadison-Singer Problem

Covariance estimation for distributions with $2+\varepsilon$ moments

An Elementary Proof of the Restricted Invertibility Theorem

See the researcher in context

Building this map preview

Nikhil Srivastava

Research overview

Is this your work?

14 publications

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

On Concentration Inequalities for Random Matrix Products

Overlaps, Eigenvalue Gaps, and Pseudospectrum under real Ginibre and Absolutely Continuous Perturbations

Scalar Poincaré Implies Matrix Poincaré

Real Stability Testing

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem

Ramanujan Graphs and the Solution of the Kadison-Singer Problem

Covariance estimation for distributions with 2+ε2+\varepsilon2+ε moments

An Elementary Proof of the Restricted Invertibility Theorem

See the researcher in context

Building this map preview

Covariance estimation for distributions with $2+\varepsilon$ moments