John Urschel

Cameron Musco, Christopher Musco, Rikhav Shah et al.

The spectral density estimation problem asks for an algorithm that, given an $n\times n$ matrix $A$, outputs a probability measure that is a good approximation to the uniform distribution on the eigenvalues of $A$, called the spectral density of $A$. This paper considers the setting where $A$ is a large normal matrix that is accessible only through matrix-vector product queries. We provide an algorithm that makes just $m$ matrix-vector queries to $A$ and returns, with high probability, a measure within earth mover's distance $O(1/m+\log m/{\sqrt n})$ of the true spectral density of $A$. We provide a complementary lower bound that any algorithm producing an $\varepsilon$-approximation to the true spectral density for large matrices must make $Ω(1/\varepsilon)$ matrix-vector queries. The lower bound holds even for the more restricted case of real symmetric input matrices. In combination with our upper bound, it shows that spectral density estimation is essentially no harder for complex normal matrices than for real symmetric matrices.

Rikhav Shah, John Urschel

The discrete Fourier transform matrix is one of the most important matrices in linear algebra, and submatrices of it arise in a variety of applications. Though the discrete Fourier transform matrix is unitary, its submatrices can be exponentially ill-conditioned, an obstacle to accurate computation. This work resolves the exact rate of the exponential ill-conditioning for square submatrices with contiguous rows and columns. As a consequence, we obtain a tight upper bound of $2 G/π$ on the exponential rate for all submatrices with contiguous columns, where $G$ is Catalan's constant. These results follow from a more general analysis of Vandermonde and Vandermonde-like matrices for which similarly tight bounds are developed.

James Chen, Alan Edelman, John Urschel

This paper introduces a number of new techniques in the study of the famous question from numerical linear algebra: what is the largest possible growth factor when performing Gaussian elimination with complete pivoting? This question is highly complex, due to a complicated set of polynomial inequalities that need to be simultaneously satisfied. This paper introduces the JuMP + Groebner basis + discriminant polynomial approach as well as the use of interval arithmetic computations. Thus, we are introducing a marriage of numerical and exact mathematical computations. In 1988, Day and Peterson performed numerical optimization on $n=5$ with NPSOL and obtained a largest seen value of $4.1325...$. This same best value was reproduced by Gould with LANCELOT in 1991. We ran extensive comparable experiments with the modern software tool JuMP and also saw the same value $4.1325...$. While the combinatorial explosion of possibilities prevents us from knowing whether there may not be a larger maximum, we succeed in obtaining the exact mathematical value: the number $4.1325...$ is exactly the root of a 61st degree polynomial provided in this work, and is a maximum given the equality constraints seen by JuMP. In light of the numerics, we pose the conjecture that this lower bound is indeed the maximum. We also apply this technique to $n = 6$, $7$, and $8$. Furthermore, in 1969, an upper bound of $4\frac{17}{18}\approx 4.94$ was produced for the maximum possible growth for $n = 5$. We slightly lower this upper bound to $4.84$.

Erik Demaine, Adam Hesterberg, Frederic Koehler et al.

Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in the statistics, machine learning, and graph drawing communities. In particular, the Kamada-Kawai force-directed graph drawing method is equivalent to MDS and is one of the most popular ways in practice to embed graphs into low dimensions. Despite its ubiquity, our theoretical understanding of MDS remains limited as its objective function is highly non-convex. In this paper, we prove that minimizing the Kamada-Kawai objective is NP-hard and give a provable approximation algorithm for optimizing it, which in particular is a PTAS on low-diameter graphs. We supplement this result with experiments suggesting possible connections between our greedy approximation algorithm and gradient-based methods.