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.
A new method improves convergence in low-rank approximation.
We accelerate the power method for strong low-rank approximation using fast sketching.
Bundle method solves low rank SDP problems without full matrix construction.
ISLET efficiently estimates low-rank tensors with optimal performance and speed.
Detecting emergence of a low-rank signal from high-dimensional data is an important problem arising from many applications such as camera surveillance and swarm monitoring using sensors. We consider a procedure based on the largest eigenvalue of the sample covariance matrix over a sliding window to detect the change. T…
This paper studies how to sketch element-wise functions of low-rank matrices. Formally, given low-rank matrix A = [Aij] and scalar non-linear function f, we aim for finding an approximated low-rank representation of the (possibly high-rank) matrix [f(Aij)]. To this end, we propose an efficient sketching-based algorithm…
New algorithm optimizes positions of CountSketch non-zero entries for better data compression.
Develops precise expressions for random projections for better machine learning tasks.
Algorithm learns a better sketch matrix for low-rank approximations.
This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modi…
Sketching reduces data size for accurate spectral estimation.
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-speci…
Randomized algorithm solves vector-valued regression problems with low-rank operators.
In this paper, we propose a general framework for sparse and low-rank tensor estimation from cubic sketchings. A two-stage non-convex implementation is developed based on sparse tensor decomposition and thresholded gradient descent, which ensures exact recovery in the noiseless case and stable recovery in the noisy cas…
The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.
Many learning tasks, such as cross-validation, parameter search, or leave-one-out analysis, involve multiple instances of similar problems, each instance sharing a large part of learning data with the others. We introduce a robust framework for solving multiple square-root LASSO problems, based on a sketch of the learn…
New algorithm reduces rank constrained optimization problems.
In this paper we present a new algorithm for computing a low rank approximation of the product by taking only a single pass of the two matrices and . The straightforward way to do this is to (a) first sketch and individually, and then (b) find the top components using PCA on the sketch. Our algori…
Sketchy reduces memory and compute requirements for adaptive regularization in deep learning.
A new algorithm reduces the time and space complexity for multinomial logistic bandits.
New algorithm converts data into sub-gaussian designs efficiently.
Improved COD algorithm reduces streaming AMM errors and uses less space.
Randomized SVD shows phase transitions in noisy data.
New algorithms solve dense linear systems with low-rank structure efficiently.
Develops an efficient method for large-scale deep learning problems.
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…
SAttention improves long sequence attention with smoothed skeleton sketching.
Random column sampling is not guaranteed to yield data sketches that preserve the underlying structures of the data and may not sample sufficiently from less-populated data clusters. Also, adaptive sampling can often provide accurate low rank approximations, yet may fall short of producing descriptive data sketches, es…
SkMM selects data for finetuning by balancing bias and variance.
This paper is concerned with the problem of low rank plus sparse matrix decomposition for big data. Conventional algorithms for matrix decomposition use the entire data to extract the low-rank and sparse components, and are based on optimization problems with complexity that scales with the dimension of the data, which…
Sketch-BERT learns vector sketches using BERT-like self-supervised learning.
TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace embedding, and therefore can be used for canonical correlation analysis, low rank approximation…
Conventional sampling techniques fall short of drawing descriptive sketches of the data when the data is grossly corrupted as such corruptions break the low rank structure required for them to perform satisfactorily. In this paper, we present new sampling algorithms which can locate the informative columns in presence …
Algorithm compresses large matrices by approximating them as low rank and low precision factors.
We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor …
We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical …
Statistical leverage scores emerged as a fundamental tool for matrix sketching and column sampling with applications to low rank approximation, regression, random feature learning and quadrature. Yet, the very nature of this quantity is barely understood. Borrowing ideas from the orthogonal polynomial literature, we in…
We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inputs and outputs of the network and can be used to quickly identify key components and summary statistics of the inputs. Furthermore, the sket…
Localized sketching improves matrix multiplication and ridge regression complexity.
We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the model. This enables memory-limited execution of several statistical analyses over streams, including online featu…
New method reduces linear regret in high-dimensional bandit problems.
New guarantees for asymmetric sketching in compressive learning.
New analysis proves sketching operators' RIP guarantees for mixture models without importance sampling.
A fast sketching algorithm solves regularized least squares problems efficiently.
A new method for estimating large-scale linear models with improved precision.
Private sketches protect linear regression data privacy.
Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner …
Sketching is a randomized dimensionality-reduction method that aims to preserve relevant information in large-scale datasets. Count sketch is a simple popular sketch which uses a randomized hash function to achieve compression. In this paper, we propose a novel extension known as Higher-order Count Sketch (HCS). While …