9 papers
Spectra of Random Polynomial Matrices: the Petaloid Law
Rikhav Shah, Edward Zeng
We study the distribution of the zeros of where is a random monic polynomial matrix, i.e., for possibly coupled rand…
Entry growth in Gaussian elimination
Rikhav Shah, John Urschel
Gaussian elimination is one of the oldest algorithms in mathematics, and the most popular method for solving an unstructured linear system. Its stability in finite precision is con…
What is Jackson's constant?
Rikhav Shah, John Urschel, Nicholas West
We prove a refinement of Jackson's theorem on the approximation of Lipschitz functions by trigonometric polynomials. Our result precisely characterizes the leading error term assoc…
Spectral density estimation for normal matrices
Cameron Musco, Christopher Musco, Rikhav Shah +2
The spectral density estimation problem asks for an algorithm that, given an matrix , outputs a probability measure that is a good approximation to the uniform distr…
The maximum-entropy median-martingale
Rikhav Shah, Vilas Winstein
This short note explores the maximum-entropy walk on the unit interval that is a median-martingale. That is, the median of its next state is equal to its current state. The station…
On the exponential rate of the condition number of Fourier submatrices and Vandermonde 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…
The Pseudospectrum of Random Compressions of Matrices
Rikhav Shah
The compression of a matrix onto a subspace is the matrix where the columns of form an orthonormal basis for . This…
Sparse Pseudospectral Shattering
Rikhav Shah, Nikhil Srivastava, Edward Zeng
The eigenvalues and eigenvectors of nonnormal matrices can be unstable under perturbations of their entries. This renders an obstacle to the analysis of numerical algorithms for no…
Fast Hermitian Diagonalization with Nearly Optimal Precision
Rikhav Shah
Algorithms for numerical tasks in finite precision simultaneously seek to minimize the number of floating point operations performed, and also the number of bits of precision requi…