BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Jess Banks

Jess Banks contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.NANumerical AnalysisData Structures and Algorithmsmath.PRComputational Complexitymath.FAmath.SPSocial and Information Networksmath-phmath.COmath.MP

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
11topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

7 published item(s)

preprint2022arXiv

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

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

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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

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

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Local Statistics, Semidefinite Programming, and Community Detection

We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into $k$ communities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The problem of detection, where we are to decide with high probability whether a graph was drawn from this model or the uniform distribution on regular graphs, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold. In this work, we consider two models of random graphs namely the well-studied (irregular) stochastic block model and a distribution over random regular graphs we'll call the Degree Regular Block Model. For both these models, we show that sufficiently high constant levels of our hierarchy can perform detection arbitrarily close to the KS threshold and that our algorithm is robust to up to a linear number of adversarial edge perturbations. Furthermore, in the case of Degree Regular Block Model (DRBM), we show that below the Kesten-Stigum threshold no constant level can do so. In the case of the (irregular) Stochastic Block Model, it is known that efficient algorithms exist all the way down to this threshold, although none are robust to a linear number of adversarial perturbations of the graph when the average degree is small. More importantly, there is little complexity-theoretic evidence that detection is hard below the threshold. In the DRBM with more than two groups, it has not to our knowledge been proven that any algorithm succeeds down to the KS threshold, let alone that one can do so robustly, and there is a similar dearth of evidence for hardness below this point.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-case computational hardness for this problem in sparse random regular graphs, showing optimality of a simple spectral certificate. This evidence takes the form of a computationally-quiet planting: we construct a distribution of d-regular graphs that has significantly smaller chromatic number than a typical regular graph drawn uniformly at random, while providing evidence that these two distributions are indistinguishable by a large class of algorithms. We generalize our results to the more general problem of certifying an upper bound on the maximum k-cut. This quiet planting is achieved by minimizing the effect of the planted structure (e.g. colorings or cuts) on the graph spectrum. Specifically, the planted structure corresponds exactly to eigenvectors of the adjacency matrix. This avoids the pushout effect of random matrix theory, and delays the point at which the planting becomes visible in the spectrum or local statistics. To illustrate this further, we give similar results for a Gaussian analogue of this problem: a quiet version of the spiked model, where we plant an eigenspace rather than adding a generic low-rank perturbation. Our evidence for computational hardness of distinguishing two distributions is based on three different heuristics: stability of belief propagation, the local statistics hierarchy, and the low-degree likelihood ratio. Of independent interest, our results include general-purpose bounds on the low-degree likelihood ratio for multi-spiked matrix models, and an improved low-degree analysis of the stochastic block model.

0 citations0 reviewsNo code linkedOpen access