BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jess Banks

Jess Banks appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.NANumerical AnalysisComputational ComplexityData Structures and AlgorithmsSocial and Information Networkscond-mat.stat-mechInformation Theorymath.FAmath.ITmath.SPmath-phmath.COmath.MP

Catalog footprint

What is connected

9works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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

Building this map preview

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

Published work

9 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
preprint2016arXiv

Information-theoretic thresholds for community detection in sparse networks

We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, consider the symmetric stochastic block model with $q$ groups, average degree $d$, and connection probabilities $c_\text{in}/n$ and $c_\text{out}/n$ for within-group and between-group edges respectively; let $λ= (c_\text{in}-c_\text{out})/(qd)$. We show that, when $q$ is large, and $λ= O(1/q)$, the critical value of $d$ at which community detection becomes possible---in physical terms, the condensation threshold---is \[ d_\text{c} = Θ\!\left( \frac{\log q}{q λ^2} \right) \, , \] with tighter results in certain regimes. Above this threshold, we show that any partition of the nodes into $q$ groups which is as `good' as the planted one, in terms of the number of within- and between-group edges, is correlated with it. This gives an exponential-time algorithm that performs better than chance; specifically, community detection becomes possible below the Kesten-Stigum bound for $q \ge 5$ in the disassortative case $λ< 0$, and for $q \ge 11$ in the assortative case $λ>0$ (similar upper bounds were obtained independently by Abbe and Sandon). Conversely, below this threshold, we show that no algorithm can label the vertices better than chance, or even distinguish the block model from an \ER\ random graph with high probability. Our lower bound on $d_\text{c}$ uses Robinson and Wormald's small subgraph conditioning method, and we also give (less explicit) results for non-symmetric stochastic block models. In the symmetric case, we obtain explicit results by using bounds on certain functions of doubly stochastic matrices due to Achlioptas and Naor; indeed, our lower bound on $d_\text{c}$ is their second moment lower bound on the $q$-colorability threshold for random graphs with a certain effective degree.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information-theoretic thresholds for community detection in sparse networks

We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, let $k$ be the number of groups, $d$ be the average degree, the probability of edges between vertices within and between groups be $c_\mathrm{in}/n$ and $c_\mathrm{out}/n$ respectively, and let $λ= (c_\mathrm{in}-c_\mathrm{out})/(kd)$. We show that, when $k$ is large, and $λ= O(1/k)$, the critical value of $d$ at which community detection becomes possible -- in physical terms, the condensation threshold -- is \[ d_c = Θ\!\left( \frac{\log k}{k λ^2} \right) \, , \] with tighter results in certain regimes. Above this threshold, we show that the only partitions of the nodes into $k$ groups are correlated with the ground truth, giving an exponential-time algorithm that performs better than chance -- in particular, detection is possible for $k \ge 5$ in the disassortative case $λ< 0$ and for $k \ge 11$ in the assortative case $λ> 0$. (Similar upper bounds were obtained independently by Abbe and Sandon.) Below this threshold, we use recent results of Neeman and Netrapalli (who generalized arguments of Mossel, Neeman, and Sly) to show that no algorithm can label the vertices better than chance, or even distinguish the block model from an Erdős-Rényi random graph with high probability. We also rely on bounds on certain functions of doubly stochastic matrices due to Achlioptas and Naor; indeed, our lower bound on $d_c$ is the second moment lower bound on the $k$-colorability threshold for random graphs with a certain effective degree.

0 citations0 reviewsNo code linkedOpen access