Matrix approximation is a common tool in machine learning for building accurate prediction models for recommendation systems, text mining, and computer vision. A prevalent assumption in constructing matrix approximations is that the partially observed matrix is of low-rank. We propose a new matrix approximation model w…
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 “Low-Rank Matrix Approximation”
The paper introduces algorithms for efficient low-rank matrix approximation.
problem Efficiently approximating large matrices while preserving their properties.
method Random linear images (sketches) of the matrix, with error bounds for quality control.
result Simple, accurate, numerically stable methods for low-rank approximation.
Paper develops a new weighted low-rank matrix approximation technique.
problem Matrix completion with missing data.
method Element-wise weighted generalization of low-rank matrix approximation.
result Proposes an algorithm and acceleration techniques for solving the weighted problem.
Low-rank matrices explain data science patterns.
problem Why do data matrices often have low rank?
method A generative model with latent variables and piecewise functions.
result Approximating large matrices with low rank is feasible.
Greedy method improves low rank matrix estimation with new approximation guarantees.
problem Low rank matrix estimation under restricted strong convexity and smoothness.
method Novel greedy algorithm analysis linking to combinatorial optimization.
result Improved approximation guarantees and statistical recovery.
New algorithm for weighted low rank approximation with provable guarantees.
problem Weighted low rank approximation (WLRA) is computationally hard.
method Reweights the low rank solution using the weight matrix itself.
result Provably optimal approximation guarantees for WLRA.
New algorithms minimize non-zero entries in low-rank approximations.
problem Minimizing non-zero entries in low-rank approximations of matrices.
method Approximation algorithms for minimizing -norm of rank- matrices.
result First provable guarantees for -Low Rank Approximation for .
Distributed algorithm finds global solutions for low-rank matrices.
problem Finding global solutions for low-rank matrices in distributed systems.
method Distributed Gradient Descent (DGD+) with LOCAL variables.
result DGD+LOCAL converges to global minimizer with exact consensus.
Algorithm learns a better sketch matrix for low-rank approximations.
problem Efficiently compute low-rank approximations of large matrices.
method Uses a learned sketch matrix instead of random matrix for optimization.
result Learned sketch matrix reduces approximation loss significantly compared to random matrix.
SketchyCGM optimizes matrices with optimal storage and low-rank solutions.
problem Optimizing matrices with low-rank solutions efficiently.
method Modifies conditional gradient method to use a small randomized sketch of the matrix variable.
result SketchyCGM converges to a low-rank solution with optimal storage.
Polynomial sketch approximates functions of low-rank matrices efficiently.
problem Approximating element-wise functions of low-rank matrices without full access.
method Combining polynomial approximation and tensor sketch for monomials.
result Efficient algorithm with lower complexity than full matrix access.
Paper solves low-rank Boolean matrix approximation using integer programming.
problem Finding low-rank approximations to Boolean matrices.
method Integer programming formulation with polynomial variables and constraints.
result First computationally tractable integer programming approach.
New method reduces computational cost for nonnegative low rank matrix approximation.
problem Efficiently compute nonnegative low rank matrix approximation for nonnegative matrices.
method Alternating projections onto tangent spaces of fixed rank matrices manifold and nonnegative matrix manifold.
result Sequence converges linearly to optimal solutions, showing better performance in terms of computational time and accuracy.
New methods recover best rank-r approximations from few entries.
problem Recovering best rank-r approximations from limited data entries.
method Two agnostic approaches: spectral truncation and projected gradient descent.
result Projected gradient descent yields superior performance.
Four conditions ensure low-rank projection costs using random matrix tricks.
problem Preserving projection costs in low-rank approximations.
method Four structural conditions using randomized matrix techniques.
result Conditions guarantee cost preservation in rank- projections.
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 nonconvex matrix completion for low-rank approximation without rank assumptions.
problem Low-rank approximation of positive semidefinite matrices from partial entries.
method Nonconvex optimization, local-minimum analysis, no spurious local minima.
result Improved sampling rate for nonconvex matrix completion with no spurious local minima.
Solves weakly supervised regression using low-rank approximations and manifold regularization.
problem Weakly supervised regression with known, unknown, and uncertain labels.
method Combines manifold regularization and low-rank matrix decomposition for optimization.
result Improves solution quality and stability for large datasets.
PSI-LinUCB improves scalability for large recommender systems.
problem Efficiently training and inferring for large action spaces in recommender systems.
method Represent inverse design matrix as diagonal + low-rank correction, derive stable rank-1 and batched updates, use projector-splitting integrator.
result Demonstrated effectiveness on recommender system datasets, achieving scalable training and inference.
Improved Frank-Wolfe method tackles nonsmooth functions.
problem Efficiently solving large nonsmooth problems with sparse structures.
method Optimizes for approximation quality over all affine approximations.
result Overcomes issues with existing nonsmooth methods in low-rank matrix estimation.
We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left an…
A hierarchical Gaussian prior model improves low-rank matrix completion.
problem Low-rank matrix completion with improved structure exploitation.
method Hierarchical Gaussian prior model with GAMP embedded variational Bayesian inference.
result The proposed method outperforms state-of-the-art matrix completion methods.
We develop an efficient algorithm for low-rank approximation with improved approximation guarantees.
problem Optimal low-rank approximation of matrices with norm constraints.
method Polynomial time column subset selection-based algorithm achieving -approximation.
result Improved approximation guarantees for low-rank approximation.
New method normalizes matrix features for robust low-rank approximation.
problem Robust feature normalization for low-rank matrix approximation.
method Learn quantile normalization operators jointly with matrix factorization.
result Improves quality of low-rank representation of data.
Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed tha…
Develops PRPCA for smooth image recovery combining low-rank and smoothness.
problem Image matrix recovery under low-rank and smoothness assumptions.
method Projected Robust PCA (PRPCA) framework combining low-rank and smoothness.
result Explicit statistical guarantees for PRPCA, reducing matrix dimensionality.
We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-no…
We accelerate the power method for strong low-rank approximation using fast sketching.
problem Efficiency bottleneck in power method for large target ranks.
method Developed an algorithmic and theoretical framework for accelerating the power method using fast sketching.
result Simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation.
Paper proposes a new convex relaxation for low-rank approximation problems.
problem Finding low-rank approximations with convex constraints in data analysis.
method Proposes a new convex relaxation using the convex envelope of the squared Frobenius norm and rank constraint.
result Solutions to the convex relaxation coincide with the original non-convex problem under certain conditions.
New method finds efficient low-rank neural networks during training.
problem High memory and computational demands of neural networks.
method Restricts weight matrices to a low-rank manifold and updates low-rank factors.
result Significantly reduced time and memory resources required for training and evaluation.
New algorithms recover low-rank matrices from few noisy projections.
problem Estimating low-rank matrices from rank-one projections with noise.
method Two fast, non-convex algorithms for matrix recovery.
result Proposed algorithms achieve linear convergence and independent sample complexity of condition number.
Introduces NMF for hyperspectral imaging and discusses its geometry and complexity.
problem Constrained low-rank matrix approximation problems.
method NMF for hyperspectral imaging, geometry and uniqueness of NMF solutions, complexity, algorithms.
result Discussion on NMF's geometry and complexity.
New method solves robust matrix completion using nonlinear equations.
problem Recover low rank and sparse matrices from incomplete observations.
method Transforms problem into solving a system of nonlinear equations, then uses the alternative direction method.
result Algorithm converges linearly to the true solution under proper assumptions.
Riemannian gradient descent escapes some spurious critical points on low-rank matrix manifold.
problem Spurious critical points on the boundary of low-rank matrix manifold.
method Riemannian gradient descent with dynamical low-rank approximation and rescaled gradient flow.
result Riemannian gradient descent escapes some spurious critical points on the boundary of the manifold.
Low-rank matrix approximations are often used to help scale standard machine learning algorithms to large-scale problems. Recently, matrix coherence has been used to characterize the ability to extract global information from a subset of matrix entries in the context of these low-rank approximations and other sampling-…
New model reduces matrix factorization bias, yielding truly low-rank solutions.
problem Gradient descent's implicit bias in matrix factorization.
method Introducing a new factorization model with constrained factors and diagonal components.
result The new model consistently exhibits a strong implicit bias, yielding truly low-rank solutions.
Simplifies solving noisy SDPs for low rank matrix recovery problems.
problem Solving SDPs with noisy data for low rank matrix recovery problems.
method Identifies conditions called simplicity to limit error in noisy SDP solutions.
result Simple SDPs can be efficiently solved and their approximate solutions trusted.
Efficient algorithm for Hadamard decomposition of matrices.
problem Decomposing matrices into low-rank factors efficiently.
method Alternating optimization with SVD-inspired initialization and momentum.
result Significantly improved performance compared to existing methods.
CUR matrix decomposition is a randomized algorithm that can efficiently compute the low rank approximation for a given rectangle matrix. One limitation with the existing CUR algorithms is that they require an access to the full matrix A for computing U. In this work, we aim to alleviate this limitation. In particular, …
Clustering analysis by nonnegative low-rank approximations has achieved remarkable progress in the past decade. However, most approximation approaches in this direction are still restricted to matrix factorization. We propose a new low-rank learning method to improve the clustering performance, which is beyond matrix f…
New algorithm improves deep learning models' robustness without sacrificing accuracy.
problem Low-rank methods compromise model robustness against adversarial perturbations.
method Robust low-rank training via approximate orthonormal constraints.
result Ensures well-conditioning and better adversarial robustness without sacrificing model accuracy.
UA-LQE improves value function learning by selectively erasing uncertain entries in Q-matrix.
problem Improving value function learning in complex reinforcement learning tasks.
method Uncertainty-aware low-rank Q-matrix estimation (UA-LQE) algorithm.
result UA-LQE selectively erases uncertain entries in Q-matrix to improve value function approximation.
Single-pass algorithm for low-rank approximation of matrix products.
problem Efficiently computing low-rank approximations of matrix products.
method A single pass algorithm that retains additional summary information about matrices A and B.
result Comparable spectral norm guarantees to existing two-pass methods with improved performance.
We describe several algorithms for matrix completion and matrix approximation when only some of its entries are known. The approximation constraint can be any whose approximated solution is known for the full matrix. For low rank approximations, similar algorithms appears recently in the literature under different name…
Algorithm compresses large matrices by approximating them as low rank and low precision factors.
problem Efficiently storing and processing large matrices with billions of elements.
method Randomized sketching and quantization of matrix columns to achieve low rank and low precision factorization.
result Achieves compression ratios as low as one bit per matrix coordinate while maintaining or improving performance.
Bundle method solves low rank SDP problems without full matrix construction.
problem Solving semidefinite programming problems with low rank solutions.
method Applying bundle method to randomly sketch matrix optimization problems and using recent results on bundle methods.
result Algorithm produces solutions with low rank representation and convergence rates.
Rank-one measurements limit feasible sets for low-rank PSD matrices.
problem Feasibility of PSD matrices under rank-one measurements.
method Characterization of feasible sets for PSD matrices given rank-one projections.
result Radius of feasible sets determines singleton solution sets for low-rank matrices.
A matrix factorization method detects text outliers using low rank approximations.
problem Challenges in detecting outliers in text data with mostly zero values.
method TONMF based on block coordinate descent (BCD) framework.
result Effective in distinguishing anomalies from natural variations in text data.