SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

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

2013-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
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}$ … 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.
View PDF Chat

Finite free convolutions of polynomials

2015-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products … We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric additive and multiplicative convolutions were introduced by Walsh and Szeg\"o in different contexts, and have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, is new. By developing the analogy with free probability, we prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these polynomials.
View PDF Chat

Twice-Ramanujan Sparsifiers

2008-01-01
Joshua Batson , Daniel A. Spielman , Nikhil Srivastava
We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our … We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{R}^{V}$, \[ x^{T}L_{G}x \leq x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot x^{T}L_{G}x \] where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.
View PDF Chat

Localization of Electrical Flows

2017-01-01
Aaron Schild , Satish Rao , Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is $O(\log^2 n)$. This is a … We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is $O(\log^2 n)$. This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is $O(\log^2 n)$. This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.
View PDF Chat

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

2022-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
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 $\delta\|M\|$ in $O(n^4+n^3\log^2(n/\delta)+\log(n/\delta)^2\log\log(n/\delta))$ floating … 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 $\delta\|M\|$ in $O(n^4+n^3\log^2(n/\delta)+\log(n/\delta)^2\log\log(n/\delta))$ floating point operations using $O(\log^2(n/\delta))$ 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).

High-girth near-Ramanujan graphs with localized eigenvectors

2019-01-01
Noga Alon , Shirshendu Ganguly , Nikhil Srivastava
We show that for every prime $d$ and $α\in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2α\log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by … We show that for every prime $d$ and $α\in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2α\log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by $(3/\sqrt{2})\sqrt{d}$, and many eigenvectors fully localized on small sets of size $O(|V|^α)$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the "scarring" phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of Erdős and Sachs for constructing high girth regular graphs.
View PDF Chat

A Spectral Approach to Polytope Diameter

2021-01-01
Hariharan Narayanan , Rikhav Shah , Nikhil Srivastava
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height … We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height of the integers and certain subdeterminants of the constraint matrix, which in some cases improves previously known results. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure $1-o(1)$ and polynomial diameter. Both bounds rely on spectral gaps -- of a certain Schr\"odinger operator in the first case, and a certain continuous time Markov chain in the second -- which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.
View PDF Chat

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

2019-01-01
Jess Banks , Archit Kulkarni , Satyaki Mukherjee +1 more
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 … 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 $\delta\in (0,1)$, every matrix $A\in \mathbb{C}^{n\times n}$ is at least $\delta\|A\|$-close to one whose eigenvectors have condition number at worst $c_n/\delta$, 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 \'Sniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.
View PDF Chat

Optimal Lower Bounds for Sketching Graph Cuts

2017-01-01
C. W. Carlson , Alexandra Kolla , Nikhil Srivastava +1 more
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an … We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on $n$ vertices up to a $1+\epsilon$ error must use $\Omega(n\log n/\epsilon^2)$ bits of space in the worst case, improving the $\Omega(n/\epsilon^2)$ bound of Andoni et al. and matching the best known upper bound achieved by spectral sparsifiers. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two $d-$regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.
View PDF Chat

Interlacing Families III: Sharper Restricted Invertibility Estimates

2017-01-01
Adam W. Marcus , Daniel A. Spielman , Nikhil Srivastava
We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. … We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. We show that the stable rank can be replaced by the Schatten 4-norm stable rank and that tighter bounds hold when the number of columns in the matrix under consideration does not greatly exceed its number of rows. Our bounds are derived from an analysis of smallest zeros of Jacobi and associated Laguerre polynomials.
View PDF Chat

Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic

2021-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the … Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the dynamics and convergence properties of the shifted QR algorithm on nonsymmetric matrices has remained elusive. We introduce a new family of shifting strategies for the Hessenberg shifted QR algorithm. We prove that when the input is a diagonalizable Hessenberg matrix $H$ of bounded eigenvector condition number $\kappa_V(H)$ -- defined as the minimum condition number of $V$ over all diagonalizations $VDV^{-1}$ of $H$ -- then the shifted QR algorithm with a certain strategy from our family is guaranteed to converge rapidly to a Hessenberg matrix with a zero subdiagonal entry, in exact arithmetic. Our convergence result is nonasymptotic, showing that the geometric mean of certain subdiagonal entries of $H$ decays by a fixed constant in every $QR$ iteration. The arithmetic cost of implementing each iteration of our strategy scales roughly logarithmically in the eigenvector condition number $\kappa_V(H)$, which is a measure of the nonnormality of $H$. The key ideas in the design and analysis of our strategy are: (1) We are able to precisely characterize when a certain shifting strategy based on Ritz values stagnates. We use this information to design certain ``exceptional shifts'' which are guaranteed to escape stagnation whenever it occurs. (2) We use higher degree shifts (of degree roughly $\log \kappa_V(H)$) to dampen transient effects due to nonnormality, allowing us to treat nonnormal matrices in a manner similar to normal matrices.

Global Convergence of Hessenberg Shifted QR I: Dynamics

2021-11-15
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the … Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the dynamics of the shifted QR algorithm on nonsymmetric matrices has remained elusive. We give a family of shifting strategies for the Hessenberg shifted QR algorithm with provably rapid global convergence on nonsymmetric matrices of bounded nonnormality, quantified in terms of the condition number of the eigenvector matrix. The convergence is linear with a constant rate, and for a well-chosen strategy from this family, the computational cost of each QR step scales nearly logarithmically in the eigenvector condition number. We perform our analysis in exact arithmetic. In the companion paper [Global Convergence of Hessenberg Shifted QR II: Numerical Stability and Deflation], we show that our shifting strategies can be implemented efficiently in finite arithmetic.
View PDF Chat

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

2022-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
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 … 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.
View PDF Chat

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

2019-01-01
Jess Banks , Jorge Garza-Vargas , Archit Kulkarni +1 more
We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $\delta>0$, computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le … We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $\delta>0$, computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le \delta$ using $O(T_{MM}(n)\log^2(n/\delta))$ arithmetic operations, in finite arithmetic with $O(\log^4(n/\delta)\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^{\omega+\eta})$ for every $\eta>0$ where $\omega$ 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}/\delta^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.

Many nodal domains in random regular graphs

2021-01-01
Shirshendu Ganguly , Theo McKenzie , Sidhanth Mohanty +1 more
Let $G$ be a random $d$-regular graph. We prove that for every constant $α> 0$, with high probability every eigenvector of the adjacency matrix of $G$ with eigenvalue less than … Let $G$ be a random $d$-regular graph. We prove that for every constant $α> 0$, with high probability every eigenvector of the adjacency matrix of $G$ with eigenvalue less than $-2\sqrt{d-2}-α$ has $Ω(n/$polylog$(n))$ nodal domains.
View PDF Chat

Scalar Poincaré Implies Matrix Poincaré

2020-01-01
Ankit Garg , Tarun Kathuria , Nikhil Srivastava
We prove that every reversible Markov semigroup which satisfies a Poincar\'e inequality satisfies a matrix-valued Poincar\'e inequality for Hermitian $d\times d$ matrix valued functions, with the same Poincar\'e constant. This … We prove that every reversible Markov semigroup which satisfies a Poincar\'e inequality satisfies a matrix-valued Poincar\'e inequality for Hermitian $d\times d$ matrix valued functions, with the same Poincar\'e 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.
View PDF Chat

A Matrix Expander Chernoff Bound

2017-01-01
Ankit Garg , Yin Tat Lee , Zhao Song +1 more
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao. Our proof is … We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves in some ways the inequality of Sutter, Berta, and Tomamichel, and may be of independent interest, as well as an adaptation of an argument for the scalar case due to Healy. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.
View PDF Chat

On Non-localization of Eigenvectors of High Girth Graphs

2018-01-01
Shirshendu Ganguly , Nikhil Srivastava
We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study … We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification

2017-01-01
Nikhil Srivastava , Luca Trevisan
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of average combinatorial degree $d$ (that is, $G$ … We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of average combinatorial degree $d$ (that is, $G$ has $dn/2$ edges) and girth $g> 2d^{1/8}+1$, and if $\lambda_1 \leq \lambda_2 \leq \cdots \lambda_n$ are the eigenvalues of the (non-normalized) Laplacian of $G$, then \[ \frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O \left( \frac 1{d^{\frac 58} }\right) \] (The Alon-Boppana theorem implies that if $G$ is unweighted and $d$-regular, then $\frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O\left( \frac 1 d \right)$ if the diameter is at least $d^{1.5}$.) Our result implies a lower bound for spectral sparsifiers. A graph $H$ is a spectral $\epsilon$-sparsifier of a graph $G$ if \[ L(G) \preceq L(H) \preceq (1+\epsilon) L(G) \] where $L(G)$ is the Laplacian matrix of $G$ and $L(H)$ is the Laplacian matrix of $H$. Batson, Spielman and Srivastava proved that for every $G$ there is an $\epsilon$-sparsifier $H$ of average degree $d$ where $\epsilon \approx \frac {4\sqrt 2}{\sqrt d}$ and the edges of $H$ are a (weighted) subset of the edges of $G$. Batson, Spielman and Srivastava also show that the bound on $\epsilon$ cannot be reduced below $\approx \frac 2{\sqrt d}$ when $G$ is a clique; our Alon-Boppana-type result implies that $\epsilon$ cannot be reduced below $\approx \frac 4{\sqrt d}$ when $G$ comes from a family of expanders of super-constant degree and super-constant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an "online" setting. We show that for the online matrix setting the $4\sqrt 2 / \sqrt d$ bound is tight, up to lower order terms.
View PDF Chat

Ramanujan Graphs and the Solution of the Kadison-Singer Problem

2014-01-01
Adam W. Marcus , Daniel A. Spielman , Nikhil Srivastava
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 … 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.
View PDF Chat

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

2013-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
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 … 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'".
View PDF Chat

An Elementary Proof of the Restricted Invertibility Theorem

2009-01-01
Daniel A. Spielman , Nikhil Srivastava
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 … 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.

Approximating the Largest Root and Applications to Interlacing Families

2017-01-01
Nima Anari , Shayan Oveis Gharan , Amin Saberi +1 more
We study the problem of approximating the largest root of a real-rooted polynomial of degree $n$ using its top $k$ coefficients and give nearly matching upper and lower bounds. We … We study the problem of approximating the largest root of a real-rooted polynomial of degree $n$ using its top $k$ coefficients and give nearly matching upper and lower bounds. We present algorithms with running time polynomial in $k$ that use the top $k$ coefficients to approximate the maximum root within a factor of $n^{1/k}$ and $1+O(\tfrac{\log n}{k})^2$ when $k\leq \log n$ and $k>\log n$ respectively. We also prove corresponding information-theoretic lower bounds of $n^{\Omega(1/k)}$ and $1+\Omega\left(\frac{\log \frac{2n}{k}}{k}\right)^2$, and show strong lower bounds for noisy version of the problem in which one is given access to approximate coefficients. This problem has applications in the context of the method of interlacing families of polynomials, which was used for proving the existence of Ramanujan graphs of all degrees, the solution of the Kadison-Singer problem, and bounding the integrality gap of the asymmetric traveling salesman problem. All of these involve computing the maximum root of certain real-rooted polynomials for which the top few coefficients are accessible in subexponential time. Our results yield an algorithm with the running time of $2^{\tilde O(\sqrt[3]n)}$ for all of them.

Asymptotically Optimal Multi-Paving

2017-01-01
Mohan Ravichandran , Nikhil Srivastava
Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings with dimension independent bounds. In … Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings with dimension independent bounds. In this paper, we develop a technique extending the arguments of Marcus, Spielman and Srivastava in their solution of the Kadison-Singer problem to show the existence of non-trivial pavings for collections of matrices. We show that given zero diagonal Hermitian contractions $A^{(1)}, \cdots, A^{(k)} \in M_n(\mathbb{C})$ and $\epsilon > 0$, one may find a paving $X_1 \amalg \cdots \amalg X_r = [n]$ where $r \leq 18k\epsilon^{-2}$ such that, \[\lambda_{max} (P_{X_i} A^{(j)} P_{X_i}) < \epsilon, \quad i \in [r], \, j \in [k].\] As a consequence, we get the correct asymptotic estimates for paving general zero diagonal matrices; zero diagonal contractions can be $(O(\epsilon^{-2}),\epsilon)$ paved. As an application, we give a simplified proof wth slightly better estimates of a theorem of Johnson, Ozawa and Schechtman concerning commutator representations of zero trace matrices.
View PDF Chat

The Solution of the Kadison-Singer Problem

2017-01-01
Adam W. Marcus , Nikhil Srivastava
These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors … These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors (along with Spielman) which appeared at the 2014 ICM. In the first part of this survey we will introduce the Kadison-Singer problem from two perspectives ($C^*$ algebras and spectral graph theory) and present some examples showing where the difficulties in solving it lie. In the second part we will develop the framework of interlacing families of polynomials, and show how it is used to solve the problem. None of the results are new, but we have added annotations and examples which we hope are of pedagogical value.

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

2015-01-01
Adam W. Marcus , Nikhil Srivastava , Daniel A. Spielman
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 … 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.
View PDF Chat

Bit Complexity of Jordan Normal Form and Spectral Factorization

2021-01-01
Papri Dey , Ravi Kannan , Nick Ryder +1 more
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{\omega+3}a+n^4a^2+n^\omega\log(1/\epsilon))$ time algorithm for finding an $\epsilon-$approximation to … We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{\omega+3}a+n^4a^2+n^\omega\log(1/\epsilon))$ time algorithm for finding an $\epsilon-$approximation to the Jordan Normal form of an integer matrix with $a-$bit entries, where $\omega$ is the exponent of matrix multiplication. (2) An $\tilde{O}(n^6d^6a+n^4d^4a^2+n^3d^3\log(1/\epsilon))$ time algorithm for $\epsilon$-approximately computing the spectral factorization $P(x)=Q^*(x)Q(x)$ of a given monic $n\times n$ rational matrix polynomial of degree $2d$ with rational $a-$bit coefficients having $a-$bit common denominators, which satisfies $P(x)\succeq 0$ for all real $x$. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in $n$ of degree at least twelve \cite{cai1994computing}. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.
View PDF Chat

On Eigenvalue Gaps of Integer Matrices

2022-01-01
Aaron Abrams , Zeph Landau , Jamie Pommersheim +1 more
Given an $n\times n$ matrix with integer entries in the range $[-h,h]$, how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap … Given an $n\times n$ matrix with integer entries in the range $[-h,h]$, how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap of $h^{-O(n)}$. Here we give an explicit construction of matrices with entries in $[0,h]$ with two eigenvalues separated by at most $h^{-n^2/16+o(n^2)}$. Up to a constant in the exponent, this agrees with the known lower bound of $\Omega((2\sqrt{n})^{-n^2}h^{-n^2})$ \cite{mahler1964inequality}. Bounds on the minimum gap are relevant to the worst case analysis of algorithms for diagonalization and computing canonical forms of integer matrices. In addition to our explicit construction, we show there are many matrices with a slightly larger gap of roughly $h^{-n^2/32}$. We also construct 0-1 matrices which have two eigenvalues separated by at most $2^{-n^2/64+o(n^2)}$.
View PDF Chat

The Complexity of Diagonalization

2023-01-01
Nikhil Srivastava
We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been … We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been studied across several research communities for decades, but many mysteries remain. We present several open problems which we hope will be of broad interest.
View PDF Chat

Support of Closed Walks and Second Eigenvalue Multiplicity of the Normalized Adjacency Matrix

2020-01-01
Theo McKenzie , Peter Rasmussen , Nikhil Srivastava
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $\Delta$ is bounded by $O(n \Delta^{7/5}/\log^{1/5-o(1)}n)$ for any $\Delta$, and by … We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $\Delta$ is bounded by $O(n \Delta^{7/5}/\log^{1/5-o(1)}n)$ for any $\Delta$, and by $O(n\log^{1/2}d/\log^{1/4-o(1)}n)$ for simple $d$-regular graphs when $d\ge \log^{1/4}n$. In fact, the same bounds hold for the number of eigenvalues in any interval of width $\lambda_2/\log_\Delta^{1-o(1)}n$ containing the second eigenvalue $\lambda_2$. The main ingredient in the proof is a polynomial (in $k$) lower bound on the typical support of a closed random walk of length $2k$ in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.
View PDF Chat

The Complexity of Diagonalization

2023-07-05
Nikhil Srivastava
We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been … We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been studied across several research communities for decades, but many mysteries remain. We present several open problems which we hope will be of broad interest.
View PDF Chat

Overlaps, eigenvalue gaps, and pseudospectrum under real Ginibre and absolutely continuous perturbations

2024-11-01
Jess Banks , Jorge Garza-Vargas , Archit Kulkarni +1 more

Ramanujan Graphs and Interlacing Families

2024-12-30
Nikhil Srivastava
This survey accompanies a lecture on the paper ``Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees'' by A. Marcus, D. Spielman, and N. Srivastava at the 2024 International Congress … This survey accompanies a lecture on the paper ``Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees'' by A. Marcus, D. Spielman, and N. Srivastava at the 2024 International Congress of Basic Science (ICBS) in July, 2024. Its purpose is to explain the developments surrounding this work over the past ten or so years, with an emphasis on connections to other areas of mathematics. Earlier surveys about the interlacing families method by the same authors focused on applications in functional analysis, whereas the focus here is on applications in spectral graph theory.
View PDF Chat

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

2025-04-24
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava

Global Convergence of Hessenberg Shifted QR II: Finite Arithmetic

2025-04-30
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava

Global Convergence of Hessenberg Shifted QR II: Finite Arithmetic

2025-04-30
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava

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

2025-04-24
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava

Ramanujan Graphs and Interlacing Families

2024-12-30
Nikhil Srivastava
This survey accompanies a lecture on the paper ``Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees'' by A. Marcus, D. Spielman, and N. Srivastava at the 2024 International Congress … This survey accompanies a lecture on the paper ``Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees'' by A. Marcus, D. Spielman, and N. Srivastava at the 2024 International Congress of Basic Science (ICBS) in July, 2024. Its purpose is to explain the developments surrounding this work over the past ten or so years, with an emphasis on connections to other areas of mathematics. Earlier surveys about the interlacing families method by the same authors focused on applications in functional analysis, whereas the focus here is on applications in spectral graph theory.
View PDF Chat

Overlaps, eigenvalue gaps, and pseudospectrum under real Ginibre and absolutely continuous perturbations

2024-11-01
Jess Banks , Jorge Garza-Vargas , Archit Kulkarni +1 more

The Complexity of Diagonalization

2023-07-05
Nikhil Srivastava
We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been … We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been studied across several research communities for decades, but many mysteries remain. We present several open problems which we hope will be of broad interest.
View PDF Chat

The Complexity of Diagonalization

2023-01-01
Nikhil Srivastava
We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been … We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been studied across several research communities for decades, but many mysteries remain. We present several open problems which we hope will be of broad interest.
View PDF Chat

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

2022-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
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 … 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.
View PDF Chat

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

2022-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
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 $\delta\|M\|$ in $O(n^4+n^3\log^2(n/\delta)+\log(n/\delta)^2\log\log(n/\delta))$ floating … 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 $\delta\|M\|$ in $O(n^4+n^3\log^2(n/\delta)+\log(n/\delta)^2\log\log(n/\delta))$ floating point operations using $O(\log^2(n/\delta))$ 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).

On Eigenvalue Gaps of Integer Matrices

2022-01-01
Aaron Abrams , Zeph Landau , Jamie Pommersheim +1 more
Given an $n\times n$ matrix with integer entries in the range $[-h,h]$, how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap … Given an $n\times n$ matrix with integer entries in the range $[-h,h]$, how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap of $h^{-O(n)}$. Here we give an explicit construction of matrices with entries in $[0,h]$ with two eigenvalues separated by at most $h^{-n^2/16+o(n^2)}$. Up to a constant in the exponent, this agrees with the known lower bound of $\Omega((2\sqrt{n})^{-n^2}h^{-n^2})$ \cite{mahler1964inequality}. Bounds on the minimum gap are relevant to the worst case analysis of algorithms for diagonalization and computing canonical forms of integer matrices. In addition to our explicit construction, we show there are many matrices with a slightly larger gap of roughly $h^{-n^2/32}$. We also construct 0-1 matrices which have two eigenvalues separated by at most $2^{-n^2/64+o(n^2)}$.
View PDF Chat

Global Convergence of Hessenberg Shifted QR I: Dynamics

2021-11-15
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the … Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the dynamics of the shifted QR algorithm on nonsymmetric matrices has remained elusive. We give a family of shifting strategies for the Hessenberg shifted QR algorithm with provably rapid global convergence on nonsymmetric matrices of bounded nonnormality, quantified in terms of the condition number of the eigenvector matrix. The convergence is linear with a constant rate, and for a well-chosen strategy from this family, the computational cost of each QR step scales nearly logarithmically in the eigenvector condition number. We perform our analysis in exact arithmetic. In the companion paper [Global Convergence of Hessenberg Shifted QR II: Numerical Stability and Deflation], we show that our shifting strategies can be implemented efficiently in finite arithmetic.
View PDF Chat

Many nodal domains in random regular graphs

2021-01-01
Shirshendu Ganguly , Theo McKenzie , Sidhanth Mohanty +1 more
Let $G$ be a random $d$-regular graph. We prove that for every constant $α&gt; 0$, with high probability every eigenvector of the adjacency matrix of $G$ with eigenvalue less than … Let $G$ be a random $d$-regular graph. We prove that for every constant $α&gt; 0$, with high probability every eigenvector of the adjacency matrix of $G$ with eigenvalue less than $-2\sqrt{d-2}-α$ has $Ω(n/$polylog$(n))$ nodal domains.
View PDF Chat

A Spectral Approach to Polytope Diameter

2021-01-01
Hariharan Narayanan , Rikhav Shah , Nikhil Srivastava
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height … We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height of the integers and certain subdeterminants of the constraint matrix, which in some cases improves previously known results. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure $1-o(1)$ and polynomial diameter. Both bounds rely on spectral gaps -- of a certain Schr\"odinger operator in the first case, and a certain continuous time Markov chain in the second -- which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.
View PDF Chat

Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic

2021-01-01
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava
Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the … Rapid convergence of the shifted QR algorithm on symmetric matrices was shown more than fifty years ago. Since then, despite significant interest and its practical relevance, an understanding of the dynamics and convergence properties of the shifted QR algorithm on nonsymmetric matrices has remained elusive. We introduce a new family of shifting strategies for the Hessenberg shifted QR algorithm. We prove that when the input is a diagonalizable Hessenberg matrix $H$ of bounded eigenvector condition number $\kappa_V(H)$ -- defined as the minimum condition number of $V$ over all diagonalizations $VDV^{-1}$ of $H$ -- then the shifted QR algorithm with a certain strategy from our family is guaranteed to converge rapidly to a Hessenberg matrix with a zero subdiagonal entry, in exact arithmetic. Our convergence result is nonasymptotic, showing that the geometric mean of certain subdiagonal entries of $H$ decays by a fixed constant in every $QR$ iteration. The arithmetic cost of implementing each iteration of our strategy scales roughly logarithmically in the eigenvector condition number $\kappa_V(H)$, which is a measure of the nonnormality of $H$. The key ideas in the design and analysis of our strategy are: (1) We are able to precisely characterize when a certain shifting strategy based on Ritz values stagnates. We use this information to design certain ``exceptional shifts'' which are guaranteed to escape stagnation whenever it occurs. (2) We use higher degree shifts (of degree roughly $\log \kappa_V(H)$) to dampen transient effects due to nonnormality, allowing us to treat nonnormal matrices in a manner similar to normal matrices.

Bit Complexity of Jordan Normal Form and Spectral Factorization

2021-01-01
Papri Dey , Ravi Kannan , Nick Ryder +1 more
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{\omega+3}a+n^4a^2+n^\omega\log(1/\epsilon))$ time algorithm for finding an $\epsilon-$approximation to … We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{\omega+3}a+n^4a^2+n^\omega\log(1/\epsilon))$ time algorithm for finding an $\epsilon-$approximation to the Jordan Normal form of an integer matrix with $a-$bit entries, where $\omega$ is the exponent of matrix multiplication. (2) An $\tilde{O}(n^6d^6a+n^4d^4a^2+n^3d^3\log(1/\epsilon))$ time algorithm for $\epsilon$-approximately computing the spectral factorization $P(x)=Q^*(x)Q(x)$ of a given monic $n\times n$ rational matrix polynomial of degree $2d$ with rational $a-$bit coefficients having $a-$bit common denominators, which satisfies $P(x)\succeq 0$ for all real $x$. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in $n$ of degree at least twelve \cite{cai1994computing}. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.
View PDF Chat

Scalar Poincaré Implies Matrix Poincaré

2020-01-01
Ankit Garg , Tarun Kathuria , Nikhil Srivastava
We prove that every reversible Markov semigroup which satisfies a Poincar\'e inequality satisfies a matrix-valued Poincar\'e inequality for Hermitian $d\times d$ matrix valued functions, with the same Poincar\'e constant. This … We prove that every reversible Markov semigroup which satisfies a Poincar\'e inequality satisfies a matrix-valued Poincar\'e inequality for Hermitian $d\times d$ matrix valued functions, with the same Poincar\'e 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.
View PDF Chat

Support of Closed Walks and Second Eigenvalue Multiplicity of the Normalized Adjacency Matrix

2020-01-01
Theo McKenzie , Peter Rasmussen , Nikhil Srivastava
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $\Delta$ is bounded by $O(n \Delta^{7/5}/\log^{1/5-o(1)}n)$ for any $\Delta$, and by … We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $\Delta$ is bounded by $O(n \Delta^{7/5}/\log^{1/5-o(1)}n)$ for any $\Delta$, and by $O(n\log^{1/2}d/\log^{1/4-o(1)}n)$ for simple $d$-regular graphs when $d\ge \log^{1/4}n$. In fact, the same bounds hold for the number of eigenvalues in any interval of width $\lambda_2/\log_\Delta^{1-o(1)}n$ containing the second eigenvalue $\lambda_2$. The main ingredient in the proof is a polynomial (in $k$) lower bound on the typical support of a closed random walk of length $2k$ in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.
View PDF Chat

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

2019-01-01
Jess Banks , Jorge Garza-Vargas , Archit Kulkarni +1 more
We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $\delta>0$, computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le … We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $\delta>0$, computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le \delta$ using $O(T_{MM}(n)\log^2(n/\delta))$ arithmetic operations, in finite arithmetic with $O(\log^4(n/\delta)\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^{\omega+\eta})$ for every $\eta>0$ where $\omega$ 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}/\delta^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.

High-girth near-Ramanujan graphs with localized eigenvectors

2019-01-01
Noga Alon , Shirshendu Ganguly , Nikhil Srivastava
We show that for every prime $d$ and $α\in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2α\log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by … We show that for every prime $d$ and $α\in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2α\log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by $(3/\sqrt{2})\sqrt{d}$, and many eigenvectors fully localized on small sets of size $O(|V|^α)$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the "scarring" phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of Erdős and Sachs for constructing high girth regular graphs.
View PDF Chat

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

2019-01-01
Jess Banks , Archit Kulkarni , Satyaki Mukherjee +1 more
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 … 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 $\delta\in (0,1)$, every matrix $A\in \mathbb{C}^{n\times n}$ is at least $\delta\|A\|$-close to one whose eigenvectors have condition number at worst $c_n/\delta$, 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 \'Sniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.
View PDF Chat

On Non-localization of Eigenvectors of High Girth Graphs

2018-01-01
Shirshendu Ganguly , Nikhil Srivastava
We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study … We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.

A Matrix Expander Chernoff Bound

2017-01-01
Ankit Garg , Yin Tat Lee , Zhao Song +1 more
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao. Our proof is … We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves in some ways the inequality of Sutter, Berta, and Tomamichel, and may be of independent interest, as well as an adaptation of an argument for the scalar case due to Healy. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.
View PDF Chat

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification

2017-01-01
Nikhil Srivastava , Luca Trevisan
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of average combinatorial degree $d$ (that is, $G$ … We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of average combinatorial degree $d$ (that is, $G$ has $dn/2$ edges) and girth $g> 2d^{1/8}+1$, and if $\lambda_1 \leq \lambda_2 \leq \cdots \lambda_n$ are the eigenvalues of the (non-normalized) Laplacian of $G$, then \[ \frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O \left( \frac 1{d^{\frac 58} }\right) \] (The Alon-Boppana theorem implies that if $G$ is unweighted and $d$-regular, then $\frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O\left( \frac 1 d \right)$ if the diameter is at least $d^{1.5}$.) Our result implies a lower bound for spectral sparsifiers. A graph $H$ is a spectral $\epsilon$-sparsifier of a graph $G$ if \[ L(G) \preceq L(H) \preceq (1+\epsilon) L(G) \] where $L(G)$ is the Laplacian matrix of $G$ and $L(H)$ is the Laplacian matrix of $H$. Batson, Spielman and Srivastava proved that for every $G$ there is an $\epsilon$-sparsifier $H$ of average degree $d$ where $\epsilon \approx \frac {4\sqrt 2}{\sqrt d}$ and the edges of $H$ are a (weighted) subset of the edges of $G$. Batson, Spielman and Srivastava also show that the bound on $\epsilon$ cannot be reduced below $\approx \frac 2{\sqrt d}$ when $G$ is a clique; our Alon-Boppana-type result implies that $\epsilon$ cannot be reduced below $\approx \frac 4{\sqrt d}$ when $G$ comes from a family of expanders of super-constant degree and super-constant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an "online" setting. We show that for the online matrix setting the $4\sqrt 2 / \sqrt d$ bound is tight, up to lower order terms.
View PDF Chat

Optimal Lower Bounds for Sketching Graph Cuts

2017-01-01
C. W. Carlson , Alexandra Kolla , Nikhil Srivastava +1 more
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an … We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on $n$ vertices up to a $1+\epsilon$ error must use $\Omega(n\log n/\epsilon^2)$ bits of space in the worst case, improving the $\Omega(n/\epsilon^2)$ bound of Andoni et al. and matching the best known upper bound achieved by spectral sparsifiers. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two $d-$regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.
View PDF Chat

Approximating the Largest Root and Applications to Interlacing Families

2017-01-01
Nima Anari , Shayan Oveis Gharan , Amin Saberi +1 more
We study the problem of approximating the largest root of a real-rooted polynomial of degree $n$ using its top $k$ coefficients and give nearly matching upper and lower bounds. We … We study the problem of approximating the largest root of a real-rooted polynomial of degree $n$ using its top $k$ coefficients and give nearly matching upper and lower bounds. We present algorithms with running time polynomial in $k$ that use the top $k$ coefficients to approximate the maximum root within a factor of $n^{1/k}$ and $1+O(\tfrac{\log n}{k})^2$ when $k\leq \log n$ and $k>\log n$ respectively. We also prove corresponding information-theoretic lower bounds of $n^{\Omega(1/k)}$ and $1+\Omega\left(\frac{\log \frac{2n}{k}}{k}\right)^2$, and show strong lower bounds for noisy version of the problem in which one is given access to approximate coefficients. This problem has applications in the context of the method of interlacing families of polynomials, which was used for proving the existence of Ramanujan graphs of all degrees, the solution of the Kadison-Singer problem, and bounding the integrality gap of the asymmetric traveling salesman problem. All of these involve computing the maximum root of certain real-rooted polynomials for which the top few coefficients are accessible in subexponential time. Our results yield an algorithm with the running time of $2^{\tilde O(\sqrt[3]n)}$ for all of them.

Localization of Electrical Flows

2017-01-01
Aaron Schild , Satish Rao , Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is $O(\log^2 n)$. This is a … We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is $O(\log^2 n)$. This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is $O(\log^2 n)$. This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.
View PDF Chat

Asymptotically Optimal Multi-Paving

2017-01-01
Mohan Ravichandran , Nikhil Srivastava
Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings with dimension independent bounds. In … Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings with dimension independent bounds. In this paper, we develop a technique extending the arguments of Marcus, Spielman and Srivastava in their solution of the Kadison-Singer problem to show the existence of non-trivial pavings for collections of matrices. We show that given zero diagonal Hermitian contractions $A^{(1)}, \cdots, A^{(k)} \in M_n(\mathbb{C})$ and $\epsilon > 0$, one may find a paving $X_1 \amalg \cdots \amalg X_r = [n]$ where $r \leq 18k\epsilon^{-2}$ such that, \[\lambda_{max} (P_{X_i} A^{(j)} P_{X_i}) < \epsilon, \quad i \in [r], \, j \in [k].\] As a consequence, we get the correct asymptotic estimates for paving general zero diagonal matrices; zero diagonal contractions can be $(O(\epsilon^{-2}),\epsilon)$ paved. As an application, we give a simplified proof wth slightly better estimates of a theorem of Johnson, Ozawa and Schechtman concerning commutator representations of zero trace matrices.
View PDF Chat

The Solution of the Kadison-Singer Problem

2017-01-01
Adam W. Marcus , Nikhil Srivastava
These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors … These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors (along with Spielman) which appeared at the 2014 ICM. In the first part of this survey we will introduce the Kadison-Singer problem from two perspectives ($C^*$ algebras and spectral graph theory) and present some examples showing where the difficulties in solving it lie. In the second part we will develop the framework of interlacing families of polynomials, and show how it is used to solve the problem. None of the results are new, but we have added annotations and examples which we hope are of pedagogical value.

Interlacing Families III: Sharper Restricted Invertibility Estimates

2017-01-01
Adam W. Marcus , Daniel A. Spielman , Nikhil Srivastava
We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. … We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. We show that the stable rank can be replaced by the Schatten 4-norm stable rank and that tighter bounds hold when the number of columns in the matrix under consideration does not greatly exceed its number of rows. Our bounds are derived from an analysis of smallest zeros of Jacobi and associated Laguerre polynomials.
View PDF Chat

Finite free convolutions of polynomials

2015-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products … We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric additive and multiplicative convolutions were introduced by Walsh and Szeg\"o in different contexts, and have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, is new. By developing the analogy with free probability, we prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these polynomials.
View PDF Chat

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

2015-01-01
Adam W. Marcus , Nikhil Srivastava , Daniel A. Spielman
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 … 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.
View PDF Chat

Ramanujan Graphs and the Solution of the Kadison-Singer Problem

2014-01-01
Adam W. Marcus , Daniel A. Spielman , Nikhil Srivastava
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 … 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.
View PDF Chat

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

2013-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
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 … 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'".
View PDF Chat

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

2013-01-01
Adam I. Marcus , Daniel A. Spielman , Nikhil Srivastava
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}$ … 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.
View PDF Chat

An Elementary Proof of the Restricted Invertibility Theorem

2009-01-01
Daniel A. Spielman , Nikhil Srivastava
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 … 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.

Twice-Ramanujan Sparsifiers

2008-01-01
Joshua Batson , Daniel A. Spielman , Nikhil Srivastava
We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our … We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{R}^{V}$, \[ x^{T}L_{G}x \leq x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot x^{T}L_{G}x \] where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.
View PDF Chat
Coauthor Papers Together
Jess Banks 9
Daniel A. Spielman 8
Jorge Garza-Vargas 8
Adam W. Marcus 4
Archit Kulkarni 3
Adam I. Marcus 3
Shirshendu Ganguly 3
Ankit Garg 2
Theo McKenzie 2
Luca Trevisan 2
Aaron Abrams 1
Ravi Kannan 1
Aaron Schild 1
Papri Dey 1
C. W. Carlson 1
Rikhav Shah 1
Noga Alon 1
Zeph Landau 1
Zhao Song 1
Hariharan Narayanan 1
Nick Ryder 1
Peter Rasmussen 1
Satish Rao 1
Jamie Pommersheim 1
Alexandra Kolla 1
Amin Saberi 1
Sidhanth Mohanty 1
Tarun Kathuria 1
Shayan Oveis Gharan 1
Yin Tat Lee 1
Joshua Batson 1
Nima Anari 1
Mohan Ravichandran 1
Satyaki Mukherjee 1

A stable, polynomial-time algorithm for the eigenpair problem

2018-04-16
Diego Armentano , Carlos Beltrán , Peter Bürgisser +2 more
We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex n \times n matrix A . These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We … We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex n \times n matrix A . These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra. A short professional video explaining the article can be found here: .
View PDF Chat

Gaussian Regularization of the Pseudospectrum and Davies’ Conjecture

2021-08-16
Jess Banks , Archit Kulkarni , Satyaki Mukherjee +1 more
Abstract A matrix is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every is the limit of diagonalizable matrices. … Abstract A matrix is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every is the limit of diagonalizable matrices. We prove a quantitative version of this fact conjectured by E. B. Davies: for each , every matrix is at least ‐close to one whose eigenvectors have condition number at worst , for some depending only on n . We further show that the dependence on δ cannot be improved to for any constant . 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. © 2021 Wiley Periodicals, Inc.
View PDF Chat

Approximate Diagonalization

2007-11-02
E. B. Davies
We describe a new method of computing functions of highly nonnormal matrices by using the concept of approximate diagonalization. We formulate a conjecture about its efficiency and provide both theoretical … We describe a new method of computing functions of highly nonnormal matrices by using the concept of approximate diagonalization. We formulate a conjecture about its efficiency and provide both theoretical and numerical evidence in support of the conjecture. We apply the method to compute arbitrary real powers of highly nonnormal matrices.

Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic

2024-08-13
Jess Banks , Jorge Garza-Vargas , Nikhil Srivastava

On the real Davies’ conjecture

2021-11-01
Vishesh Jain , Ashwin Sah , Mehtaab Sawhney
We show that every matrix A∈Rn×n is, at least, δ‖A‖-close to a real matrix A+E∈Rn×n whose eigenvectors have condition number, at most, O˜n(δ−1). In fact, we prove that, with high … We show that every matrix A∈Rn×n is, at least, δ‖A‖-close to a real matrix A+E∈Rn×n whose eigenvectors have condition number, at most, O˜n(δ−1). In fact, we prove that, with high probability, taking E to be a sufficiently small multiple of an i.i.d. real sub-Gaussian matrix of bounded density suffices. This essentially confirms a speculation of Davies and of Banks, Kulkarni, Mukherjee and Srivastava, who recently proved such a result for i.i.d. complex Gaussian matrices. Along the way we also prove nonasymptotic estimates on the minimum possible distance between any two eigenvalues of a random matrix whose entries have arbitrary means; this part of our paper may be of independent interest.

Matrix regularizing effects of Gaussian perturbations

2017-02-17
Michael Aizenman , Ron Peled , Jeffrey Schenker +2 more
The addition of noise has a regularizing effect on Hermitian matrices. This effect is studied here for [Formula: see text], where [Formula: see text] is the base matrix and [Formula: … The addition of noise has a regularizing effect on Hermitian matrices. This effect is studied here for [Formula: see text], where [Formula: see text] is the base matrix and [Formula: see text] is sampled from the GOE or the GUE random matrix ensembles. We bound the mean number of eigenvalues of [Formula: see text] in an interval, and present tail bounds for the distribution of the Frobenius and operator norms of [Formula: see text] and for the distribution of the norm of [Formula: see text] applied to a fixed vector. The bounds are uniform in [Formula: see text] and exceed the actual suprema by no more than multiplicative constants. The probability of multiple eigenvalues in an interval is also estimated.
View PDF Chat

Smoothed analysis of algorithms

2004-05-01
Daniel A. Spielman , Shang‐Hua Teng
We introduce the smoothed analysis of algorithms , which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the … We introduce the smoothed analysis of algorithms , which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has smoothed complexity polynomial in the input size and the standard deviation of Gaussian perturbations.

COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME

1994-12-01
Jin‐Yi Cai
Given a rational matrix A, and a set of rational matrices B, C,… which commute with A, we give polynomial time algorithms to compute exactly the Jordan Normal Form of … Given a rational matrix A, and a set of rational matrices B, C,… which commute with A, we give polynomial time algorithms to compute exactly the Jordan Normal Form of A, as well as the transformed matrices of B, C,…. We also obtain the transformation matrix and its inverse exactly in polynomial time.

Lyapunov theorems for operator algebras

1991-01-01
Charles A. Akemann , Joel Anderson

Explicit construction of linear sized tolerant networks

1988-12-01
Noga Alon , Fan Chung
View PDF Chat

ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION

1989-05-01
Zhaojun Bai , James Demmel
The usual QR algorithm for finding the eigenvalues of a Hessenberg matrix H is based on vector-vector operations, e.g. adding a multiple of one row to another. The opportunities for … The usual QR algorithm for finding the eigenvalues of a Hessenberg matrix H is based on vector-vector operations, e.g. adding a multiple of one row to another. The opportunities for parallelism in such an algorithm are limited. In this paper, we describe a reorganization of the QR algorithm to permit either matrix-vector or matrix-matrix operations to be performed, both of which yield more efficient implementations on vector and parallel machines. The idea is to chase a k by k bulge rather than a 1 by 1 or 2 by 2 bulge as in the standard QR algorithm. We report our preliminary numerical experiments on the CONVEX C-1 and CYBER 205 vector machines.

The transmission of shifts and shift blurring in the QR algorithm

1996-07-01
David S. Watkins

Low Rank Perturbation of Jordan Structure

2003-01-01
Julio Moro , Froilán M. Dopico
Let A be a matrix and $\lambda_0$ be one of its eigenvalues having g elementary Jordan blocks in the Jordan canonical form of A. We show that for most matrices … Let A be a matrix and $\lambda_0$ be one of its eigenvalues having g elementary Jordan blocks in the Jordan canonical form of A. We show that for most matrices B satisfying ${\rm rank}\,(B)\leq g$, the Jordan blocks of A+B with eigenvalue $\lambda_0$ are just the $g-{\rm rank}\,(B)$ smallest Jordan blocks of A with eigenvalue $\lambda_0$. The set of matrices for which this behavior does not happen is explicitly characterized through a scalar determinantal equation involving B and some of the $\lambda_0$-eigenvectors of A. Thus, except for a set of zero Lebesgue measure, a low rank perturbation A+B of A destroys for each of its eigenvalues exactly the rank,(B) largest Jordan blocks of A, while the rest remain unchanged.

Some new asymptotic properties for the zeros of Jacobi, Laguerre, and Hermite polynomials

1995-06-01
Holger Dette , W. J. Studden
View PDF Chat

Random Matrices: the Distribution of the Smallest Singular Values

2010-03-11
Terence Tao , Van Vu
View PDF Chat

On condition numbers and the distance to the nearest ill-posed problem

1987-05-01
James Demmel

A note on the largest eigenvalue of a large dimensional sample covariance matrix

1988-08-01
Zhidong Bai , Jack W. Silverstein , Yanqing Yin

Condition numbers of random matrices

1991-06-01
Stanisław J. Szarek

Small Ball Probabilities for Linear Images of High-Dimensional Distributions

2014-12-04
Mark Rudelson , Roman Vershynin
We study concentration properties of random vectors of the form |$AX$|⁠, where |$X = (X_1,\ldots , X_n)$| has independent coordinates and |$A$| is a given matrix. We show that the … We study concentration properties of random vectors of the form |$AX$|⁠, where |$X = (X_1,\ldots , X_n)$| has independent coordinates and |$A$| is a given matrix. We show that the distribution of |$AX$| is well spread in space whenever the distributions of |$X_i$| are well spread on the line. Specifically, assume that the probability that |$X_i$| falls in any given interval of length |$t$| is at most |$p$|⁠. Then the probability that |$AX$| falls in any given ball of radius |$t \|A\|_{\mathrm {HS}}$| is at most |$(Cp)^{0.9 r(A)}$|⁠, where |$r(A)$| denotes the stable rank of |$A$| and |$C$| is an absolute constant.
View PDF Chat

The Effect of Aggressive Early Deflation on the Convergence of the QR Algorithm

2008-01-01
Daniel Kreßner
Aggressive early deflation has proven to significantly enhance the convergence of the QR algorithm for computing the eigenvalues of a nonsymmetric matrix. One purpose of this paper is to point … Aggressive early deflation has proven to significantly enhance the convergence of the QR algorithm for computing the eigenvalues of a nonsymmetric matrix. One purpose of this paper is to point out that this deflation strategy is equivalent to extracting converged Ritz vectors from certain Krylov subspaces. As a special case, the single-shift QR algorithm enhanced with aggressive early deflation corresponds to a Krylov subspace method whose starting vector undergoes a Rayleigh-quotient iteration. It is shown how these observations can be used to derive improved convergence bounds for the QR algorithm.
View PDF Chat

A new similarity transformation method for eigenvalues and eigenvectors

1974-10-01
Alex N. Beavers , Eugene D. Denman

The Distribution of the Determinant of a Complex Wishart Distributed Matrix

1963-03-01
N. R. Goodman
View PDF Chat

The Condition Number of Equivalence Transformations That Block Diagonalize Matrix Pencils

1983-06-01
James Demmel
How ill-conditioned must a matrix S be if its columns are constrained to span certain subspaces? We answer this question in order to find nearly best conditioned matrices $S_R $ … How ill-conditioned must a matrix S be if its columns are constrained to span certain subspaces? We answer this question in order to find nearly best conditioned matrices $S_R $ and $S_L $ that block diagonalize a given matrix pencil $T = A + \lambda B$, i.e. $S_L^{ - 1} TS_R = \Theta $ is block diagonal. We show that the best conditioned $S_R $ has a condition number approximately equal to the cosecant of the smallest angle between right subspaces belonging to different diagonal blocks of $\Theta $. Thus, the more nearly the right subspaces overlap the more ill-conditioned $S_R $ must be. The same is true of $S_L $ and the left subspaces. For the standard eigenproblem $(T = A - \lambda I)$, $S_L = S_R $ and the cosecant of the angle between subspaces turns out equal to an earlier estimate of the smallest condition number, namely the norm of the projection matrix associated with one of the subspaces. We apply this result to bound the error in an algorithm to compute analytic functions of matrices, for instance exp $(T)$.

On the second eigenvalue of a graph

1991-08-01
A. Nilli

A Randomized Homotopy for the Hermitian Eigenpair Problem

2014-10-22
Diego Armentano , Felipe Cucker

Local fluctuation of the spectrum of a multidimensional Anderson tight binding model

1996-04-01
Nariyuki Minami
View PDF Chat

Computing an Eigenvector with Inverse Iteration

1997-01-01
Ilse C. F. Ipsen
The purpose of this paper is two-fold: to analyze the behavior of inverse iteration for computing a single eigenvector of a complex square matrix and to review Jim Wilkinson's contributions … The purpose of this paper is two-fold: to analyze the behavior of inverse iteration for computing a single eigenvector of a complex square matrix and to review Jim Wilkinson's contributions to the development of the method. In the process we derive several new results regarding the convergence of inverse iteration in exact arithmetic. In the case of normal matrices we show that residual norms decrease strictly monotonically. For eighty percent of the starting vectors a single iteration is enough. In the case of non-normal matrices, we show that the iterates converge asymptotically to an invariant subspace. However, the residual norms may not converge. The growth in residual norms from one iteration to the next can exceed the departure of the matrix from normality. We present an example where the residual growth is exponential in the departure of the matrix from normality. We also explain the often significant regress of the residuals after the first iteration: it occurs when the non-normal part of the matrix is large compared to the eigenvalues of smallest magnitude. In this case computing an eigenvector with inverse iteration is exponentially ill conditioned (in exact arithmetic). We conclude that the behavior of the residuals in inverse iteration is governed by the departure of the matrix from normality rather than by the conditioning of a Jordan basis or the defectiveness of eigenvalues.
View PDF Chat

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

2004-06-13
Daniel A. Spielman , Shang‐Hua Teng
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the … We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.
View PDF Chat

Inverse Iteration, Ill-Conditioned Equations and Newton’s Method

1979-07-01
Gareth W. Peters , J. H. Wilkinson
Inverse iteration is one of the most widely used algorithms in practical linear algebra but an understanding of its main numerical properties has developed piecemeal over the last thirty years: … Inverse iteration is one of the most widely used algorithms in practical linear algebra but an understanding of its main numerical properties has developed piecemeal over the last thirty years: a major source of misunderstanding is that it requires the solution of very ill-conditioned systems of equations. We describe closely related algorithms which avoid these ill-conditioned systems and explain why the standard inverse iteration algorithm may nevertheless be preferable. The discussion covers the generalized problems $Ax - \lambda Bx$ and $(A_r \lambda ^r + \cdots + A_1 \lambda + A_0 )x = 0$ in addition to the standard problem. The case when $A - \lambda I$ is almost singular to the working accuracy has only recently been understood, mainly through the work of Varah. The final sections give a detailed account of the current state of this work, concluding with an analysis based on the singular value decomposition.

The behavior of eigenvalues and singular values under perturbations of restricted rank

1976-01-01
Robert C. Thompson

The Matrix Sign Function Method and the Computation of Invariant Subspaces

1997-07-01
Ralph Byers , Chunyang He , Volker Mehrmann
A perturbation analysis shows that if a numerically stable procedure is used to compute the matrix sign function, then it is competitive with conventional methods for computing invariant subspaces. Stability … A perturbation analysis shows that if a numerically stable procedure is used to compute the matrix sign function, then it is competitive with conventional methods for computing invariant subspaces. Stability analysis of the Newton iteration improves an earlier result of Byers and confirms that ill-conditioned iterates may cause numerical instability. Numerical examples demonstrate the theoretical results.
View PDF Chat

Random matrices: Universality of ESDs and the circular law

2010-08-17
Terence Tao , Van Vu , Manjunath Krishnapur
Given an n×n complex matrix A, let $$\mu_{A}(x,y):=\frac{1}{n}|\{1\le i\le n,\operatorname{Re}\lambda_{i}\le x,\operatorname{Im}\lambda_{i}\le y\}|$$ be the empirical spectral distribution (ESD) of its eigenvalues λi∈ℂ, i=1, …, n. We consider the limiting distribution … Given an n×n complex matrix A, let $$\mu_{A}(x,y):=\frac{1}{n}|\{1\le i\le n,\operatorname{Re}\lambda_{i}\le x,\operatorname{Im}\lambda_{i}\le y\}|$$ be the empirical spectral distribution (ESD) of its eigenvalues λi∈ℂ, i=1, …, n. We consider the limiting distribution (both in probability and in the almost sure convergence sense) of the normalized ESD $\mu_{{1}/{\sqrt{n}}A_{n}}$ of a random matrix An=(aij)1≤i, j≤n, where the random variables aij−E(aij) are i.i.d. copies of a fixed random variable x with unit variance. We prove a universality principle for such ensembles, namely, that the limit distribution in question is independent of the actual choice of x. In particular, in order to compute this distribution, one can assume that x is real or complex Gaussian. As a related result, we show how laws for this ESD follow from laws for the singular value distribution of $\frac{1}{\sqrt{n}}A_{n}-zI$ for complex z. As a corollary, we establish the circular law conjecture (both almost surely and in probability), which asserts that $\mu_{{1}/{\sqrt{n}}A_{n}}$ converges to the uniform measure on the unit disc when the aij have zero mean.
View PDF Chat

A Krylov--Schur Algorithm for Large Eigenproblems

2002-01-01
G. W. Stewart
Sorensen's implicitly restarted Arnoldi algorithm is one of the most successful and flexible methods for finding a few eigenpairs of a large matrix. However, the need to preserve the structure … Sorensen's implicitly restarted Arnoldi algorithm is one of the most successful and flexible methods for finding a few eigenpairs of a large matrix. However, the need to preserve the structure of the Arnoldi decomposition on which the algorithm is based restricts the range of transformations that can be performed on the decomposition. In consequence, it is difficult to deflate converged Ritz vectors from the decomposition. Moreover, the potential forward instability of the implicit QR algorithm can cause unwanted Ritz vectors to persist in the computation. In this paper we introduce a general Krylov decomposition that solves both problems in a natural and efficient manner.

Computing Rational Forms of Integer Matrices

2002-09-01
Mark Giesbrecht , Arne Storjohann

The Littlewood–Offord problem and invertibility of random matrices

2008-03-11
Mark Rudelson , Roman Vershynin
View PDF Chat

The Kadison–Singer problem in discrepancy theory

2003-09-11
Nik Weaver
View PDF Chat

Forward Instability of Tridiagonal QR

1993-01-01
Beresford Ν. Parlett , Jian Le
he QR algorithm is the standard method for finding all the eigenvalues of a symmetric tridiagonal matrix. It produces a sequence of similar tridiagonals. It is well known that the … he QR algorithm is the standard method for finding all the eigenvalues of a symmetric tridiagonal matrix. It produces a sequence of similar tridiagonals. It is well known that the QR transformation from T to $\hat{T} $ is backward stable. That means that the computed $\hat{T} $ is exactly orthogonally similar to a matrix close to T. It is also known that sometimes the computed $\hat{T} $ is not close to the exact $\hat{T} $. This is caused by the occasional extreme sensitivity of $\hat{T} $ to changes in T or the shift, and will be referred to as forward instability of the (computed) QR algorithm. For the purpose of computing eigenvalues the property of backward stability is all that is required. However, the QR transformation has other uses and then forward stability is needed. This paper gives examples, analyzes the forward instability, and shows that it occurs only when the shift causes “premature deflation.” It is shown that forward stability is governed by the size of the last entry in normalized eigenvectors of leading principal submatrices, and the extreme values of the derivative of each entry in $\hat{T} $ as a function of the shift are found.

On the limit of the largest eigenvalue of the large dimensional sample covariance matrix

1988-08-01
Yanqing Yin , Zhidong Bai , P. R. Krishnaiah
View PDF Chat

The single ring theorem

2011-07-29
Alice Guionnet , Manjunath Krishnapur , Ofer Zeitouni
We study the empirical measure LA n of the eigenvalues of nonnormal square matrices of the form An = UnTnVn with Un, Vn independent Haar distributed on the unitary group … We study the empirical measure LA n of the eigenvalues of nonnormal square matrices of the form An = UnTnVn with Un, Vn independent Haar distributed on the unitary group and Tn real diagonal.We show that when the empirical measure of the eigenvalues of Tn converges, and Tn satisfies some technical conditions, LA n converges towards a rotationally invariant measure µ on the complex plane whose support is a single ring.In particular, we provide a complete proof of the Feinberg-Zee single ring theorem [6].We also consider the case where Un, Vn are independently Haar distributed on the orthogonal group.
View PDF Chat

Random Regularization of Brown Spectral Measure

2002-08-01
Piotr Śniady
View PDF Chat

The Kadison–Singer Problem in mathematics and engineering

2006-02-03
Peter G. Casazza , Janet C. Tremain
We will see that the famous intractible 1959 Kadison-Singer Problem in C*-algebras is equivalent to fundamental open problems in a dozen different areas of research in mathematics and engineering. This … We will see that the famous intractible 1959 Kadison-Singer Problem in C*-algebras is equivalent to fundamental open problems in a dozen different areas of research in mathematics and engineering. This work gives all these areas common ground on which to interact as well as explaining why each area has volumes of literature on their respective problems without a satisfactory resolution.
View PDF Chat

Expanders via random spanning trees

2009-01-04
Navin Goyal , Luis Rademacher , Santosh Vempala
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that … Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph Gn, p, for p = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by Aldous and Broder: A random walk in the graph with edges leading to previously unvisited vertices included in the tree. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).

Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

2006-01-01
Arvind Sankar , Daniel A. Spielman , Shang‐Hua Teng
Let Å be an arbitrary matrix and let A be a slight random perturbation of Å. We prove that it is unlikely that A has a large condition number. Using … Let Å be an arbitrary matrix and let A be a slight random perturbation of Å. We prove that it is unlikely that A has a large condition number. Using this result, we prove that it is unlikely that A has large growth factor under Gaussian elimination without pivoting. By combining these results, we show that the smoothed precision necessary to solve Ax = b, for any b, using Gaussian elimination without pivoting is logarithmic. Moreover, when Å is an all-zero square matrix, our results significantly improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 18 (1997), pp. 499-517).
View PDF Chat

Restricted Invertibility Revisited

2017-01-01
Assaf Naor , Pierre Youssef

On a problem of Kadison and Singer.

1991-09-01
Lior Tzafriri , Jean Bourgain

A Remark on Perturbations of Compact Operators.

1994-06-01
Lars Hörmander , Anders Melin
View PDF Chat

The distribution of overlaps between eigenvectors of Ginibre matrices

2019-11-14
Paul Bourgade , Guillaume Dubach
View PDF Chat

Random matrices: Overcrowding estimates for the spectrum

2018-06-26
Hoi H. Nguyen
View PDF Chat

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

2006-01-01
Daniel A. Spielman , Shang‐Hua Teng
We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y … We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990). For any symmetric, weakly diagonally-dominant matrix A with non-positive off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a preconditioner B of A with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero off-diagonal entries such that the finite generalized condition number $\kappa_{f} (A,B)$ is at most k, for some other constant c. In the special case when the nonzero structure of the matrix is planar the corresponding linear system solver runs in expected time $ O (n \log^{2} n + n \log n \ \log \log n \ \log (1/\epsilon))$. We hope that our introduction of algorithms of low asymptotic complexity will lead to the development of algorithms that are also fast in practice.
View PDF Chat

Eigenvalues of rank one perturbations of unstructured matrices

2012-04-01
André C. M. Ran , Michał Wojtylak
View PDF Chat