arXiv research

Improved matrix approximation using randomized algorithms.

Paper proposes diagnostics for error and variance estimation in randomized matrix computations.

In this paper, we present a new framework to obtain tail inequalities for sums of random matrices. Compared with existing works, our tail inequalities have the following characteristics: 1) high feasibility--they can be used to study the tail behavior of various matrix functions, e.g., arbitrary matrix norms, the absol…

Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower …

This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random ve…

HD algorithm simulates dynamics on random matrix ensembles without generating full matrices.

RandNLA uses randomness for matrix problems in machine learning.

Extends spectral number variance convergence to random matrix ensembles for twisted Laplacians.

We introduce a covariance matrix estimator that both takes into account the heteroskedasticity of financial returns (by using an exponentially weighted moving average) and reduces the effective dimensionality of the estimation (and hence measurement noise) via techniques borrowed from random matrix theory. We calculate…

Study evaluates thresholds for removing noise from DNN weights using random matrix theory.

Matrices satisfying the Restricted Isometry Property (RIP) play an important role in the areas of compressed sensing and statistical learning. RIP matrices with optimal parameters are mainly obtained via probabilistic arguments, as explicit constructions seem hard. It is therefore interesting to ask whether a fixed mat…

Random matrix theory predicts neural representations generalize well.

Generalizes randomized SVD for better matrix approximations using Gaussian vectors.

The paper analyzes stability of random matrix products with Markovian noise.

Paper develops new patterns for unique matrix completions.

A parameterization that is a modified version of a previous work is proposed for the returns and correlation matrix of financial time series and its properties are studied. This parameterization allows easy introduction of non-stationarity and it shows several of the characteristics of the true, observed realizations, …

Improves detection of low-rank signals from noisy data matrices.

Study on neural network initialization with shaped infinite depth-and-width networks.

This paper presents a sequential randomized lowrank matrix factorization approach for incrementally predicting values of an unknown function at test points using the Gaussian Processes framework. It is well-known that in the Gaussian processes framework, the computational bottlenecks are the inversion of the (regulariz…

Reservoir computing's success depends on mapping different input time series to separable states.

Study on signal-plus-noise decomposition in nonlinear spiked random matrices.

We discuss the question of how to pick a matrix uniformly (in an appropriate sense) at random from groups big and small. We give algorithms in some cases, and indicate interesting problems in others.

New method for faster graph parameter inference from large random Kronecker graphs.

Study on random matrices in deep neural networks with IID entries.

We derive exponential tail inequalities for sums of random matrices with no dependence on the explicit matrix dimensions. These are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the dimens…

The Random Parameters model was proposed to explain the structure of the covariance matrix in problems where most, but not all, of the eigenvalues of the covariance matrix can be explained by Random Matrix Theory. In this article, we explore other properties of the model, like the scaling of its PDF as one take larger …

U-Net trained to recover acoustic interference striations from distorted data.

We show how random matrix theory can be applied to develop new algorithms to extract dynamic factors from macroeconomic time series. In particular, we consider a limit where the number of random variables N and the number of consecutive time measurements T are large but the ratio N / T is fixed. In this regime the unde…

CovRegRF estimates covariance matrix from covariates using random forests.

Short proof shows how ridge regression works with random data.

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $L_α(G)=D-\sum_{r=1}^dα_rD(D^{-1}A)^r$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $α=(α_1...α_d)$ are nonn…

Improved perturbation reduces matrix condition number to O(n) with minimal storage.

Gradient Descent with small random initialization solves rank-1 matrix completion efficiently.

The high-order relations between the content in social media sharing platforms are frequently modeled by a hypergraph. Either hypergraph Laplacian matrix or the adjacency matrix is a big matrix. Randomized algorithms are used for low-rank factorizations in order to approximately decompose and eventually invert such big…

Relying on recent advances in statistical estimation of covariance distances based on random matrix theory, this article proposes an improved covariance and precision matrix estimation for a wide family of metrics. The method is shown to largely outperform the sample covariance matrix estimate and to compete with state…

Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decomposition (rSVD). Firstly, two fast randomized algorithms (rSVD-PI and rSVD- BKI) are proposed for handling …

New matrix ensembles better match deep neural network spectral densities.

We introduce a "learning-based" algorithm for the low-rank decomposition problem: given an $n \times d$ matrix $A$, and a parameter $k$, compute a rank-$k$ matrix $A'$ that minimizes the approximation loss $\|A-A'\|_F$. The algorithm uses a training set of input matrices in order to optimize its performance. Specifical…

New algorithms estimate matrix norms without matrix multiplication.

We confirm universal behaviors such as eigenvalue distribution and spacings predicted by Random Matrix Theory (RMT) for the cross correlation matrix of the daily stock prices of Tokyo Stock Exchange from 1993 to 2001, which have been reported for New York Stock Exchange in previous studies. It is shown that the random …

The paper analyzes data augmentation for precision matrix estimation in high dimensions.

Random feature maps are ubiquitous in modern statistical machine learning, where they generalize random projections by means of powerful, yet often difficult to analyze nonlinear operators. In this paper, we leverage the "concentration" phenomenon induced by random matrix theory to perform a spectral analysis on the Gr…

Paper uses Random Matrix Theory for optimal training-testing data split.

Random matrix theory explains how neural networks adapt to data.

Study reveals an equivalence principle for the spectrum of random inner-product kernel matrices in polynomial scaling.

Gradient descent proves global convergence for 4-layer matrix factorization.

Paper analyzes AIRL in high-dimensional spaces using random matrix theory.

The covariance matrix of a $p$-dimensional random variable is a fundamental quantity in data analysis. Given $n$ i.i.d. observations, it is typically estimated by the sample covariance matrix, at a computational cost of $O(np^{2})$ operations. When $n,p$ are large, this computation may be prohibitively slow. Moreover, …