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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,341 papers · 148 categories
Trend · papers per month
48 results for “random matrix analysis”
We analyze random feature maps for high-dimensional data using spectral methods.
problem Understanding the spectrum of random feature maps for high-dimensional data.
method We use concentration phenomena from random matrix theory to analyze the Gram matrix of random feature maps for Gaussian mixture models.
result Our results provide insights into the interplay between nonlinearity and data statistics.
Short proof shows how ridge regression works with random data.
problem Understanding prediction error in ridge regression with random design.
method Combination of exchangeability arguments, matrix perturbation, and operator convexity.
result Elementary proof of prediction error without complex inequalities.
This work analyzes self-attention matrices using random matrix theory.
problem Understanding the theoretical behavior of self-attention layers in neural networks.
method Asymptotic spectral analysis of the attention matrix, Gaussian equivalence, and linearization.
result The singular value distribution of the attention matrix is asymptotically characterized by a linear model.
The study analyzes LS-SVM performance using random matrix theory.
problem Performance analysis of LS-SVM in large dimensional settings.
method Random matrix theory applied to LS-SVM performance analysis.
result The LS-SVM decision function is asymptotically normal.
A unified error analysis for randomized low-rank approximation with application to data assimilationmath.NA
Unified error analysis for low-rank approximation improves data assimilation performance.
problem Analyzing the error in low-rank approximation methods for data assimilation.
method Unified stochastic analysis framework for Frobenius norm error bounds on centered and non-standard Gaussian matrices.
result Unified bounds provide clearer interpretations and enable better practical choices for covariance matrices.
Study analyzes perturbations in singular subspaces under random noise.
problem Understanding singular vector and subspace changes in signal-plus-noise models.
method Generalized Davis-Kahan-Wedin theorem for any unitarily invariant norm, considering and bounds.
result Fine-grained insights into singular vector and subspace perturbations, including and bounds.
Paper combines matrix factorization and random walk models for node embeddings.
problem Learning node representations in graphs for applications like link prediction and node classification.
method Proposes a weighted matrix factorization model using kernel functions to incorporate random walk-based information.
result The proposed model outperforms existing node embedding algorithms in link prediction and node classification tasks.
RandNLA uses randomness for matrix problems in machine learning.
problem Matrix problems in machine learning.
method Randomized Numerical Linear Algebra.
result New challenges in RandNLA due to hardware trends and advances in ML.
Improved covariance estimation for various metrics outperforms existing methods.
problem Estimating covariance and precision matrices for a wide range of metrics.
method Random matrix theory for improved estimation.
result Significantly outperforms sample covariance matrix and state-of-the-art methods.
Improved SVD for shifted matrices without explicit matrix construction.
problem Efficiently estimating SVD of shifted matrices.
method Shifted Randomized SVD algorithm.
result More efficient matrix factorization and low-rank approximation.
Determining the number of factors in a forecast model by a random matrix test: cryptocurrenciesq-fin.ST
Study uses random matrix test to find significant factors in cryptocurrency forecasts.
problem Determining the optimal number of factors in cryptocurrency forecast models.
method Applied a random matrix test to a forecast model of Reduced Rank Regression (RRR) on cryptocurrencies.
result Consistent results with visual inspection, minimal computational cost compared to cross-validation.
The paper analyzes data augmentation for precision matrix estimation in high dimensions.
problem Precision matrix estimation in high-dimensional settings.
method Linear shrinkage estimators and data augmentation methods.
result Concentration bounds for the quadratic error of estimators.
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…
Study shows double descent curve in high-dimensional linear regression with random projections.
problem Understanding the generalization performance in high-dimensional settings with random projections.
method Fixed prediction problem, ridge regression estimator, minimum norm least-squares fit, random matrix theory, asymptotic equivalents.
result Exhibit a double descent curve for high-dimensional linear regression with random projections.
New tail inequalities for sums of random matrices without matrix-dimension terms.
problem Tail behavior of matrix functions in high-dimensional settings.
method Developed new tail inequalities for matrix sums, independent of matrix dimension.
result Tail inequalities for various matrix functions without matrix-dimension terms.
Improved perturbation reduces matrix condition number to O(n) with minimal storage.
problem Reducing the condition number of deterministic matrices for efficient algorithmic use.
method Introduced pattern matrices and sparse perturbations with dependent entries.
result Condition number reduced to O(n) with O(n) random numbers in O(log n) precision.
Paper studies tensor models using random matrix theory.
problem Analyzing asymmetric order-d spiked tensor models with Gaussian noise.
method Uses variational definition of singular vectors and values, constructs equivalent spiked symmetric block-wise random matrix from tensor contractions.
result Characterizes asymptotic singular values and alignments of singular vectors with true spike components.
Identifying Relevant Eigenimages - a Random Matrix Approachphysics.data-an
Dimensional reduction of high dimensional data can be achieved by keeping only the relevant eigenmodes after principal component analysis. However, differentiating relevant eigenmodes from the random noise eigenmodes is problematic. A new method based on the random matrix theory and a statistical goodness-of-fit test i…
Reservoir computing's success depends on mapping different input time series to separable states.
problem Quantifying the ability of random linear reservoirs to map different input time series.
method Mathematical framework using spectral properties of the connectivity matrix.
result Separation capacity is fully characterized by the spectral properties of the connectivity matrix.
Random matrix analysis reveals that neural network weights are mostly random, with some indicating learned information.
problem Understanding how neural networks store information needed for tasks.
method Random matrix theory (RMT) applied to weight matrices of trained deep neural networks.
result Most singular values and eigenvectors of trained neural networks follow universal RMT predictions, suggesting they are random and do not contain system-specific information.
New method avoids spurious critical points for low-rank matrix recovery.
problem Low-rank matrix recovery problems on Riemannian manifold.
method Riemannian gradient descent with random initialization.
result Riemannian gradient descent avoids spurious critical points and converges nearly linearly.
Study on tensor signal estimation from incomplete data.
problem Estimating a rank-one tensor signal from noisy, incomplete data.
method Reduction to random matrix model for spectral analysis.
result Loss of performance due to incomplete data.
The paper explores states of financial markets using correlation matrices and their dynamics.
problem Understanding the states of financial markets based on correlations.
method Revisits previous work and introduces recent developments in practical applications.
result Analysis of trajectories and symbolic dynamics in correlation matrix space.
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial where is the adjacency matrix of a weighted, undirected graph, is the diagonal matrix of weighted degrees, and are nonn…
Random matrix theory explains how neural networks adapt to data.
problem Understanding how neural networks learn and generalize from data.
method Random matrix analysis of two-layer neural networks.
result Sharp characterization of feature spectrum and generalization error.
Characterizes RFF regression in large setting, providing precise learning phases and double descent curve.
problem Characterizes RFF regression in large setting.
method Characterizes the exact asymptotics of random Fourier feature (RFF) regression in the realistic setting of large .
result Characterizes two qualitatively different phases of learning and the corresponding double descent test error curve.
Active covariance estimation using random sub-sampling of variable subsets.
problem Estimating covariance matrices for partially observed random vectors.
method Unbiased covariance estimator under a model of partially observed variables and active learning framework.
result Derivation of error bounds revealing relations between sub-sampling probabilities and covariance matrix entries.
New algorithm tackles non-convex matrix completion in semi-random settings.
problem Matrix completion in semi-random environments with varying observation probabilities.
method Proposes a pre-processing step to re-weight semi-random input, followed by a nearly-linear time algorithm.
result Recovering ground-truth matrix using non-convex local minima after pre-processing.
A new method for streaming KPCA reduces space and time requirements.
problem Efficiently processing large, non-linear data sets in streaming environments.
method Combines random feature maps with matrix sketching techniques.
result Guaranteed spectral norm error bounds and improved space efficiency.
Gradient descent solves rank-one matrix estimation problem with detailed time evolution analysis.
problem Estimating a rank-one symmetric matrix corrupted by noise.
method Gradient descent on a sphere, using local versions of the semi-circle law.
result Explicit formulas for the time evolution of the estimator and cost function, revealing phase transitions.
We provide a unified analysis of the predictive risk of ridge regression and regularized discriminant analysis in a dense random effects model. We work in a high-dimensional asymptotic regime where and , and allow for arbitrary covariance among the features. For both metho…
The paper analyzes stability of random matrix products with Markovian noise.
problem Analyzing stability of random matrix products with Markovian noise.
method Using a super-Lyapunov drift condition and controlled growth of matrix-valued functions, the paper provides an exponential stability result for the p-th moment of random matrix product.
result Finite-time p-th moment bounds for linear stochastic approximation and TD learning algorithms.
New tools in nonlinear random matrices improve understanding of the Sum of Squares hierarchy.
problem Improving the Sum of Squares (SoS) hierarchy's performance on average-case problems.
method Developed new tools in nonlinear random matrices and applied them to analyze the SoS hierarchy.
result Subexponential-time SoS lower bounds for various problems, offering evidence for the low-degree likelihood ratio hypothesis.
Gradient descent proves global convergence for 4-layer matrix factorization.
problem Global convergence of gradient descent on four-layer matrix factorization under random initialization.
method New techniques to show saddle-avoidance properties and extend eigenvalue theories.
result Polynomial-time global convergence guarantee for randomly initialized gradient descent on four-layer matrix factorization.
A new method uses SPDEs to efficiently model random fields on complex domains.
problem Efficient representation of random fields on complex domains for engineering and machine learning.
method Uses SPDEs to develop a scalable framework for statFEM and GP regression.
result Can model anisotropic, non-stationary random fields with arbitrary smoothness.
Simplifies matrix completion with statistical models.
problem Matrix completion under MCAR assumption.
method Statistical models and missing data analysis.
result Matrix completion valid without MCAR assumption.
Improved SVRG for quadratic functions achieves better performance and running times.
problem Minimizing quadratic functions with a specific type of Hessian matrix.
method Variant of SVRG algorithm for quadratic functions with improved analysis.
result Improved performance and running times for quadratic functions compared to state-of-the-art methods.
Complex network analysis reveals dominant stocks in financial stock returns correlations.
problem Inferring financial stock returns correlations from complex network analysis.
method Simulated geometric Brownian motion for stocks, complex network analysis, eigenvector centrality, clustering.
result Returns correlation matrix is dominated by stocks with high eigenvector centrality and clustering.
Improves detection of low-rank signals from noisy data matrices.
problem Statistical detection of low-rank signals in noisy data matrices.
method Entrywise pre-transforming data matrix for non-Gaussian noise, sharp phase transition thresholds, central limit theorem for linear spectral statistics, hypothesis test.
result Improves detection of low-rank signals from noisy data matrices, generalizing known results.
New analysis reveals optimal regularization for ESNs, avoiding double descent.
problem Characterizing and optimizing Echo State Networks (ESNs) for precise bias-variance.
method Random matrix theory applied to ESNs in a teacher-student setting.
result ESNs achieve lower MSE with limited training samples and teacher memory.
The paper analyzes how random perturbations affect RSVD and its applications.
problem Analyzing the impact of random perturbations on RSVD.
method Derives bounds for distances between exact and approximated singular vectors using RSVD.
result Established nearly-optimal convergence rates and asymptotic normality for RSVD in various inference problems.
A scalable framework for clustering large graphs using randomized sketching.
problem Clustering large partially observed graphs efficiently.
method Randomized graph sketching, correlation-based retrieval, uniform and degree-based node sampling.
result Improved phase transitions for clustering with reduced computational complexity and minimum cluster size.
Randomized SVD shows phase transitions in noisy data.
problem Noise sensitivity of randomized SVD in large rank matrices.
method Analyzed R-SVD under low-rank signal plus noise model.
result R-SVD exhibits BBP-like phase transition with outliers above detectability threshold.
New method for faster graph parameter inference from large random Kronecker graphs.
problem Efficiently infer graph parameters from large random Kronecker graphs.
method Decompose adjacency matrix into signal and noise components, then use denoising and solving approach.
result Proposed method achieves comparable or better performance than existing methods at lower computational cost.
New matrix ensembles better match deep neural network spectral densities.
problem Theoretical spectral density models for deep networks do not match empirical observations.
method Introduced new matrix ensemble classes to better fit observed spectral densities.
result Theoretical models for deep networks are significantly flawed.
Random Matrix Theory Analysis of Cross Correlations in Financial Marketscond-mat.stat-mech
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 …
Gradient Descent with small random initialization solves rank-1 matrix completion efficiently.
problem Matrix completion for rank-1 symmetric matrices.
method Gradient Descent with small random initialization.
result Gradient Descent converges to the ground truth for rank-1 symmetric matrix completion.