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 …
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “randomized matrix multiplications”
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…
Study proposes memory-efficient backpropagation for linear layers in neural networks.
problem Significant memory usage in backpropagation through linear layers in neural networks.
method Randomized matrix multiplications to reduce memory usage with a moderate decrease in test accuracy.
result Demonstrated benefits of the proposed method on fine-tuning pre-trained models.
New algorithms estimate matrix norms without matrix multiplication.
problem Estimating matrix norms efficiently in a matrix-free setting.
method Randomized algorithms based on Hutchinson's estimator modifications.
result Oracle complexity bounds for two-to-infinity and one-to-two norms.
Expected centre of mass for random embeddings is constant.
problem Understanding the expected centre of mass for random embeddings.
method Analyzing the Haar measure and Gaussian unitary ensemble on SL(N, C).
result The expectation of the centre of mass is a constant multiple of the identity matrix.
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…
A new method combines multiple cancer datasets to improve analysis.
problem Combining multiple cancer datasets for comprehensive analysis.
method Multiple Augmented Reduced Rank Regression (maRRR) method.
result Improved power and insights from combining multiple cancer datasets.
Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank- projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These condit…
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factorscs.DS
We prove optimal subspace embedding conjecture up to sub-polylogarithmic factors.
problem Optimal dimension and sparsity of subspace embeddings.
method Iterative decoupling technique to analyze higher-order trace moment bounds.
result Sub-polylogarithmic factors in dimension and sparsity of subspace embeddings.
We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlike MMW, where every step requires full matrix exponentiation, our steps require only a single product of the form , which the Lanczos …
Unified analysis of generalization curves in large models using gradient flow.
problem Analyzing generalization error curves in simple learning models.
method Gradient flow in the Gaussian covariate model, using random matrix theory.
result Unified understanding of multiple descent structures in learning curves.
We present a new trace estimator of the matrix whose explicit form is not given but its matrix multiplication to a vector is available. The form of the estimator is similar to the Hutchison stochastic trace estimator, but instead of the random noise vectors in Hutchison estimator, we use small number of probing vectors…
New algorithm for active learning in multiple matrix completion problems.
problem Simultaneous matrix completion with unknown ranks and varying sizes.
method MAlocate algorithm that adapts to unknown ranks and sizes.
result Minimax-optimal performance demonstrated with lower-bound analysis.
We introduce a "learning-based" algorithm for the low-rank decomposition problem: given an matrix , and a parameter , compute a rank- matrix that minimizes the approximation loss . The algorithm uses a training set of input matrices in order to optimize its performance. Specifical…
We propose improved methods to identify stock groups using the correlation matrix of stock price changes. By filtering out the marketwide effect and the random noise, we construct the correlation matrix of stock groups in which nontrivial high correlations between stocks are found. Using the filtered correlation matrix…
We develop a method to describe laws of random surfaces using surface holonomy.
problem Describing laws of random surfaces with structure.
method Introduce surface holonomy and develop expected surface developments.
result Expected surface development provides a structured description of random surface laws.
Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-…
MCE reduces embedding instability in nonlinear dimensionality reduction.
problem Embedding instability caused by random initialization.
method Median of multiple embeddings (MCE) based on large deviation theory.
result MCE achieves consistency at an exponential rate and effectively mitigates instability.
Random projections (RP) are a popular tool for reducing dimensionality while preserving local geometry. In many applications the data set to be projected is given to us in advance, yet the current RP techniques do not make use of information about the data. In this paper, we provide a computationally light way to extra…
The matrix-based Renyi's α-order entropy functional was recently introduced using the normalized eigenspectrum of a Hermitian matrix of the projected data in a reproducing kernel Hilbert space (RKHS). However, the current theory in the matrix-based Renyi's α-order entropy functional only defines the entropy of a single…
The study uses Random Matrix Theory to identify structural changes in stock markets during shocks.
problem Understanding structural changes in stock markets during exogenous shocks.
method Random Matrix Theory and complexity gap analysis.
result The complexity gap collapses during shocks, indicating strong synchronization, and widens before shocks, signaling a rich structure.
Improved statistical computation through efficient matrix sampling.
problem Reducing computational cost in large-scale statistical methods.
method Accumulative sub-sampling method to improve statistical efficiency.
result Effective matrix size control improves computational efficiency.
In recent years, randomized methods for numerical linear algebra have received growing interest as a general approach to large-scale problems. Typically, the essential ingredient of these methods is some form of randomized dimension reduction, which accelerates computations, but also creates random approximation error.…
Mixed membership factorization is a popular approach for analyzing data sets that have within-sample heterogeneity. In recent years, several algorithms have been developed for mixed membership matrix factorization, but they only guarantee estimates from a local optimum. Here, we derive a global optimization (GOP) algor…
Efficient approximations reduce computation of matrix-based Renyi's entropy.
problem High computational complexity of matrix-based Renyi's entropy.
method Taylor, Chebyshev, and Lanczos approximations to reduce complexity.
result Reduced complexity to significantly less than with negligible accuracy loss.
We use a cluster ensemble to determine the number of clusters, k, in a group of data. A consensus similarity matrix is formed from the ensemble using multiple algorithms and several values for k. A random walk is induced on the graph defined by the consensus matrix and the eigenvalues of the associated transition proba…
We find a novel correlation structure in the residual noise of stock market returns that is remarkably linked to the composition and stability of the top few significant factors driving the returns, and moreover indicates that the noise band is composed of multiple subbands that do not fully mix. Our findings allow us …
Cleaning large correlation matrices: tools from random matrix theorycond-mat.stat-mech
This review covers recent results concerning the estimation of large covariance matrices using tools from Random Matrix Theory (RMT). We introduce several RMT methods and analytical techniques, such as the Replica formalism and Free Probability, with an emphasis on the Marchenko-Pastur equation that provides informatio…
New method for inference on covariates in NMF with random effects.
problem Formal inference for covariate effects in NMF with non-negativity constraints.
method NMF-RE model with random effects, ridge updates, df-based cap, asymptotic linearization, wild bootstrap.
result Valid inference on covariates with non-negativity constraint, avoiding degeneracy.
Paper studies quantized LRMR with random dithering for correlated tasks.
problem Estimating coefficient matrix in quantized multivariate regression.
method Uniform quantization with random dithering, constrained and regularized Lasso estimators.
result Achieves minimax optimal rate with dithering, slightly worsens quantization effect.
Advances in molecular "omics'" technologies have motivated new methodology for the integration of multiple sources of high-content biomedical data. However, most statistical methods for integrating multiple data matrices only consider data shared vertically (one cohort on multiple platforms) or horizontally (different …
A novel framework for consensus clustering is presented which has the ability to determine both the number of clusters and a final solution using multiple algorithms. A consensus similarity matrix is formed from an ensemble using multiple algorithms and several values for k. A variety of dimension reduction techniques …
This paper optimizes matrix-based Renyi's entropy computation for large datasets.
problem Efficiently calculating matrix-based Renyi's entropy for large-scale applications.
method Develops randomized approximations for matrix-based Renyi's entropy with arbitrary α orders.
result Achieves a significant reduction in time complexity from O(n^3) to O(n^2sm), where s, m << n.
Matrix sketching is a recently developed data compression technique. An input matrix A is efficiently approximated with a smaller matrix B, so that B preserves most of the properties of A up to some guaranteed approximation ratio. In so doing numerical operations on big data sets become faster. Sketching algorithms gen…
New algorithms solve dense linear systems with low-rank structure efficiently.
problem Solving dense linear systems with specific singular value conditions.
method Randomized algorithms using matrix sketching and low-rank update formulas.
result Achieves nearly-linear time complexity for solving such systems.
New method extrapolates spectral densities from smaller models to larger ones.
problem Limited practical computations for large machine learning models.
method Algebraic spectral curve theory for free decompression.
result Framework enables extrapolation of spectral densities with multiple or multi-modal bulks.
The paper infers multiple graphs from stationary signals on them.
problem Inferring multiple graphs from signals observed on their nodes.
method Convex optimization method leveraging matrix polynomial commutation.
result High-probability bounds on recovery error provided.
Sparse OSEs achieve optimal embedding dimension of O(d).
problem Achieving optimal embedding dimension for sparse OSEs.
method Random sparsified matrix with non-zeros per column.
result Sparse OSEs can achieve embedding dimension , improving on previous .
Generalised matrix-matrix multiplication forms the kernel of many mathematical algorithms. A faster matrix-matrix multiply immediately benefits these algorithms. In this paper we implement efficient matrix multiplication for large matrices using the floating point Intel Pentium SIMD (Single Instruction Multiple Data) a…
Explains deep learning models and their geometric properties.
problem Understanding the geometric intuition behind deep learning models.
method Geometrical intuition and novel insights into loss surfaces of deep learning models.
result Deep neural networks carve out manifolds with multiplication neurons.
We consider the problem of efficient randomized dimensionality reduction with norm-preservation guarantees. Specifically we prove data-dependent Johnson-Lindenstrauss-type geometry preservation guarantees for Ho's random subspace method: When data satisfy a mild regularity condition -- the extent of which can be estima…
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time . The funda…
New insights into learning rates and batch sizes for neural networks using random matrix theory.
problem Understanding how batch size affects learning rates in neural networks.
method Random matrix theory applied to spiked, field-dependent random matrices.
result Analytical expressions for maximal learning rates as a function of batch size.
A new method for efficient nonlinear process monitoring using random Bernoulli features.
problem High computational demands and real-time responsiveness in online monitoring systems.
method Random Bernoulli principal component analysis to capture nonlinear patterns efficiently.
result The proposed methods offer excellent scalability and reduced computational complexity.
This letter proposes a dictionary learning algorithm for blind one bit compressed sensing. In the blind one bit compressed sensing framework, the original signal to be reconstructed from one bit linear random measurements is sparse in an unknown domain. In this context, the multiplication of measurement matrix $\Ab$ an…
Newton-LESS sparsifies Gaussian sketching for faster optimization.
problem Computing the Hessian matrix in optimization is computationally expensive.
method Uses a sparsified version of a dense Gaussian sketching matrix.
result Achieves nearly the same convergence rate as dense Gaussian embeddings without the computational cost.
Proposes a new Gaussian factor for probabilistic inference with degenerate settings.
problem Handling linear dependencies among random variables in Gaussian networks.
method Introduces a parametrised factor that relaxes the positive-definite constraint of the covariance matrix.
result Accurately accommodates degeneracies in probabilistic inference without significant computational overhead.
On the overlaps between eigenvectors of correlated random matricescond-mat.stat-mech
We obtain general, exact formulas for the overlaps between the eigenvectors of large correlated random matrices, with additive or multiplicative noise. These results have potential applications in many different contexts, from quantum thermalisation to high dimensional statistics. We find that the overlaps only depend …