Source author record

Archit Kulkarni

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

ResearcherUnclaimed source record

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

Catalog footprint

Research overview

9works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2022arXiv

Spectra of infinite graphs via freeness with amalgamation

We use tools from free probability to study the spectra of Hermitian operators on infinite graphs. Special attention is devoted to universal covering trees of finite graphs. For operators on these graphs we derive a new variational formula for the spectral radius and provide new proofs of results due to Sunada and Aomoto using free probability. With the goal of extending the applicability of free probability techniques beyond universal covering trees, we introduce a new combinatorial product operation on graphs and show that, in the non-commutative probability context, it corresponds to the notion of freeness with amalgamation. We show that Cayley graphs of amalgamated free products of groups, as well as universal covering trees, can be constructed using our graph product.

preprint2020arXiv

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

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

preprint2020arXiv

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

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

preprint2020arXiv

The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

We study the Lanczos algorithm where the initial vector is sampled uniformly from $\mathbb{S}^{n-1}$ . Let $A$ be an $n \times n$ Hermitian matrix. We show that when run for few iterations, the output of Lanczos on $A$ is almost deterministic. More precisely, we show that for any $\varepsilon \in (0, 1)$ there exists $c >0$ depending only on $\varepsilon$ and a certain global property of the spectrum of $A$ (in particular, not depending on $n$ ) such that when Lanczos is run for at most $c \log n$ iterations, the output Jacobi coefficients deviate from their medians by $t$ with probability at most $\exp(-n^\varepsilon t^2)$ for $t<\Vert A \Vert$ . We directly obtain a similar result for the Ritz values and vectors. Our techniques also yield asymptotic results: Suppose one runs Lanczos on a sequence of Hermitian matrices $A_n \in M_n(\mathbb{C})$ whose spectral distributions converge in Kolmogorov distance with rate $O(n^{-\varepsilon})$ to a density $μ$ for some $\varepsilon > 0$ . Then we show that for large enough $n$ , and for $k=O(\sqrt{\log n})$ , the Jacobi coefficients output after $k$ iterations concentrate around those for $μ$ . The asymptotic setting is relevant since Lanczos is often used to approximate the spectral density of an infinite-dimensional operator by way of the Jacobi coefficients; our result provides some theoretical justification for this approach. In a different direction, we show that Lanczos fails with high probability to identify outliers of the spectrum when run for at most $c' \log n$ iterations, where again $c'$ depends only on the same global property of the spectrum of $A$ . Classical results imply that the bound $c' \log n$ is tight up to a constant factor.

preprint2014arXiv

A Generalization of Fibonacci Far-Difference Representations and Gaussian Behavior

A natural generalization of base B expansions is Zeckendorf's Theorem: every integer can be uniquely written as a sum of non-consecutive Fibonacci numbers $\{F_n\}$ , with $F_{n+1} = F_n + F_{n-1}$ and $F_1=1, F_2=2$ . If instead we allow the coefficients of the Fibonacci numbers in the decomposition to be zero or $\pm 1$ , the resulting expression is known as the far-difference representation. Alpert proved that a far-difference representation exists and is unique under certain restraints that generalize non-consecutiveness, specifically that two adjacent summands of the same sign must be at least 4 indices apart and those of opposite signs must be at least 3 indices apart. We prove that a far-difference representation can be created using sets of Skipponacci numbers, which are generated by recurrence relations of the form $S^{(k)}_{n+1} = S^{(k)}_{n} + S^{(k)}_{n-k}$ for $k \ge 0$ . Every integer can be written uniquely as a sum of the $\pm S^{(k)}_n$ 's such that every two terms of the same sign differ in index by at least 2k+2, and every two terms of opposite signs differ in index by at least k+2. Additionally, we prove that the number of positive and negative terms in given Skipponacci decompositions converges to a Gaussian, with a computable correlation coefficient that is a rational function of the smallest root of the characteristic polynomial of the recurrence. The proof uses recursion to obtain the generating function for having a fixed number of summands, which we prove converges to the generating function of a Gaussian. We next explore the distribution of gaps between summands, and show that for any k the probability of finding a gap of length $j \ge 2k+2$ decays geometrically, with decay ratio equal to the largest root of the given k-Skipponacci recurrence. We conclude by finding sequences that have an (s,d) far-difference representation for any positive integers s,d.

preprint2014arXiv

Sets Characterized by Missing Sums and Differences in Dilating Polytopes

A sum-dominant set is a finite set $A$ of integers such that $|A+A| > |A-A|$ . As a typical pair of elements contributes one sum and two differences, we expect sum-dominant sets to be rare in some sense. In 2006, however, Martin and O'Bryant showed that the proportion of sum-dominant subsets of $\{0,\dots,n\}$ is bounded below by a positive constant as $n\to\infty$ . Hegarty then extended their work and showed that for any prescribed $s,d\in\mathbb{N}_0$ , the proportion $ρ^{s,d}_n$ of subsets of $\{0,\dots,n\}$ that are missing exactly $s$ sums in $\{0,\dots,2n\}$ and exactly $2d$ differences in $\{-n,\dots,n\}$ also remains positive in the limit. We consider the following question: are such sets, characterized by their sums and differences, similarly ubiquitous in higher dimensional spaces? We generalize the integers in a growing interval to the lattice points in a dilating polytope. Specifically, let $P$ be a polytope in $\mathbb{R}^D$ with vertices in $\mathbb{Z}^D$ , and let $ρ_n^{s,d}$ now denote the proportion of subsets of $L(nP)$ that are missing exactly $s$ sums in $L(nP)+L(nP)$ and exactly $2d$ differences in $L(nP)-L(nP)$ . As it turns out, the geometry of $P$ has a significant effect on the limiting behavior of $ρ_n^{s,d}$ . We define a geometric characteristic of polytopes called local point symmetry, and show that $ρ_n^{s,d}$ is bounded below by a positive constant as $n\to\infty$ if and only if $P$ is locally point symmetric. We further show that the proportion of subsets in $L(nP)$ that are missing exactly $s$ sums and at least $2d$ differences remains positive in the limit, independent of the geometry of $P$ . A direct corollary of these results is that if $P$ is additionally point symmetric, the proportion of sum-dominant subsets of $L(nP)$ also remains positive in the limit.

preprint2014arXiv

Sums and differences of correlated random sets

Many fundamental questions in additive number theory (such as Goldbach's conjecture, Fermat's last theorem, and the Twin Primes conjecture) can be expressed in the language of sum and difference sets. As a typical pair of elements contributes one sum and two differences, we expect that $|A-A| > |A+A|$ for a finite set $A$ . However, in 2006 Martin and O'Bryant showed that a positive proportion of subsets of $\{0, \dots, n\}$ are sum-dominant, and Zhao later showed that this proportion converges to a positive limit as $n \to \infty$ . Related problems, such as constructing explicit families of sum-dominant sets, computing the value of the limiting proportion, and investigating the behavior as the probability of including a given element in $A$ to go to zero, have been analyzed extensively. We consider many of these problems in a more general setting. Instead of just one set $A$ , we study sums and differences of pairs of \emph{correlated} sets $(A,B)$ . Specifically, we place each element $a \in \{0,\dots, n\}$ in $A$ with probability $p$ , while $a$ goes in $B$ with probability $ρ_1$ if $a \in A$ and probability $ρ_2$ if $a \not \in A$ . If $|A+B| > |(A-B) \cup (B-A)|$ , we call the pair $(A,B)$ a \emph{sum-dominant $(p,ρ_1, ρ_2)$ -pair}. We prove that for any fixed $\vecρ=(p, ρ_1, ρ_2)$ in $(0,1)^3$ , $(A,B)$ is a sum-dominant $(p,ρ_1, ρ_2)$ -pair with positive probability, and show that this probability approaches a limit $P(\vecρ)$ . Furthermore, we show that the limit function $P(\vecρ)$ is continuous. We also investigate what happens as $p$ decays with $n$ , generalizing results of Hegarty-Miller on phase transitions. Finally, we find the smallest sizes of MSTD pairs.

preprint2013arXiv

Generalizing Zeckendorf's Theorem to f-decompositions

A beautiful theorem of Zeckendorf states that every positive integer can be uniquely decomposed as a sum of non-consecutive Fibonacci numbers $\{F_n\}$ , where $F_1 = 1$ , $F_2 = 2$ and $F_{n+1} = F_n + F_{n-1}$ . For general recurrences $\{G_n\}$ with non-negative coefficients, there is a notion of a legal decomposition which again leads to a unique representation, and the number of summands in the representations of uniformly randomly chosen $m \in [G_n, G_{n+1})$ converges to a normal distribution as $n \to \infty$ . We consider the converse question: given a notion of legal decomposition, is it possible to construct a sequence $\{a_n\}$ such that every positive integer can be decomposed as a sum of terms from the sequence? We encode a notion of legal decomposition as a function $f:\N_0\to\N_0$ and say that if $a_n$ is in an " $f$ -decomposition", then the decomposition cannot contain the $f(n)$ terms immediately before $a_n$ in the sequence; special choices of $f$ yield many well known decompositions (including base- $b$ , Zeckendorf and factorial). We prove that for any $f:\N_0\to\N_0$ , there exists a sequence $\{a_n\}_{n=0}^\infty$ such that every positive integer has a unique $f$ -decomposition using $\{a_n\}$ . Further, if $f$ is periodic, then the unique increasing sequence $\{a_n\}$ that corresponds to $f$ satisfies a linear recurrence relation. Previous research only handled recurrence relations with no negative coefficients. We find a function $f$ that yields a sequence that cannot be described by such a recurrence relation. Finally, for a class of functions $f$ , we prove that the number of summands in the $f$ -decomposition of integers between two consecutive terms of the sequence converges to a normal distribution.

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.

Archit Kulkarni

Research overview

Is this your work?

9 publications

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

Spectra of infinite graphs via freeness with amalgamation

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

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

The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

A Generalization of Fibonacci Far-Difference Representations and Gaussian Behavior

Sets Characterized by Missing Sums and Differences in Dilating Polytopes

Sums and differences of correlated random sets

Generalizing Zeckendorf's Theorem to f-decompositions

See the researcher in context

Building this map preview