Paper proposes a new technique to compress CNNs while maintaining accuracy.
problem CNNs struggle with traditional low-rank approximation methods, leading to degraded accuracy.
method Introduces a training technique that finds a flat minimum in low-rank approximation without a decomposed structure.
result CNN models can be compressed with higher accuracy and lower computation than conventional methods.
Paper tackles fair low-rank approximation and column subset selection.
problem Minimize loss over sub-populations in machine learning.
method Developed algorithms for fair low-rank approximation and fair column subset selection.
result Achieved polynomial time algorithms for fair low-rank approximation.
In this paper, we propose a low-rank approximation method based on discrete least-squares for the approximation of a multivariate function from random, noisy-free observations. Sparsity inducing regularization techniques are used within classical algorithms for low-rank approximation in order to exploit the possible sp…
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 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.
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…
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 ℓ0-norm of rank-k matrices. result First provable guarantees for ℓ0-Low Rank Approximation for k>1. We develop an efficient algorithm for low-rank approximation with improved approximation guarantees.
problem Optimal low-rank approximation of matrices with ℓ1 norm constraints. method Polynomial time column subset selection-based algorithm achieving ildeO(k1/2)-approximation. result Improved approximation guarantees for ℓ1 low-rank approximation. The study assesses low-rank approximations in Gaussian Process regression.
problem Improving Gaussian Process regression efficiency with low-rank approximations.
method Analyzes two low-rank approximations: random Fourier features and Mercer expansion truncation.
result Bounds on the divergence and error between exact and approximate GP models.
The study assesses low-rank approximations in Gaussian Process regression.
problem Improving the efficiency of Gaussian Process regression while maintaining accuracy.
method Analyzes two low-rank approximations: random Fourier features and Mercer expansion truncation, and bounds the divergence and error between exact and approximate models.
result Theoretical bounds on the divergence and error between exact and approximate Gaussian Process models are provided.
Solves low-rank approximation problems in Hilbert spaces.
problem Low-rank approximation in Hilbert spaces.
method Closed-form solutions and error bounds for bounded linear operators.
result Generalization to bounded linear operators from finite dimensions.
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.
Efficiently reduces tensor ranks using mean-field approximation.
problem Low-rank approximation of non-negative tensors.
method Mean-field approximation of tensor rank reduction.
result Our algorithm achieves faster and competitive tensor rank reduction.
New method for initializing low-rank neural networks improves performance.
problem Training low-rank neural networks efficiently and accurately.
method Inspired by function approximation, proposes a novel low-rank initialization framework.
result Demonstrates significant gap between spectral and low-rank initialization approaches.
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.
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.
Matrices of (approximate) low rank are pervasive in data science, appearing in recommender systems, movie preferences, topic models, medical records, and genomics. While there is a vast literature on how to exploit low rank structure in these datasets, there is less attention on explaining why the low rank structure ap…
Paper develops fast low-rank approximation for smoothing splines.
problem Computational infeasibility of fitting cubic smoothing splines to large datasets.
method Low-rank approximation using eigensystem truncation.
result The method provides accurate, fast estimates with error bounds.
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.
Stochastic gradient descent on manifolds improves low-rank approximation.
problem Efficiently approximate large matrices with lower rank.
method Stochastic gradient descent on a manifold.
result Algorithm outperforms Euclidean space methods on Netflix Prize data.
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.
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.
We propose a new framework for the analysis of low-rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank SVD for matrices and multi-linear SVD for tensors. Then, building …
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.
Simple algorithms improve ℓp-norm low-rank approximations.
problem Efficiently approximating matrices with low rank using ℓp norms. method Non-convex gradient-based algorithms with polynomial time complexity.
result Achieves (1+ε)-OPT approximations. 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.
The paper reviews Hankel low-rank methods for time series analysis and forecasting.
problem Developing efficient methods for time series analysis and forecasting.
method Hankel low-rank approximation and completion techniques.
result Discussion of methods and challenges in obtaining optimal solutions.
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.
Paper improves tensor approximation for streaming data.
problem Challenges in finding accurate low-tubal-rank tensor approximations in streaming settings.
method Extends Frequent Directions for efficient low-tubal-rank tensor approximation.
result The new algorithm achieves arbitrarily small approximation error with linear sketch size growth.
The problem of low-rank approximation with convex constraints, which appears in data analysis, system identification, model order reduction, low-order controller design and low-complexity modelling is considered. Given a matrix, the objective is to find a low-rank approximation that meets rank and convex constraints, w…
We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminisce…
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.
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.
This work tackles sparse coding in DLRA for interpretable multiway data.
problem Sparse coding in DLRA for interpretable multiway data.
method Proposes a new sparse-coding subproblem (MSC) and several algorithms to solve it.
result DLRA extends low-rank approximations, reducing variance and enhancing interpretability.
We simplify SSL by approximating redundant structural components with low-rank factorization.
problem Improving self-supervised learning performance with limited labeled data.
method Low-rank approximation of structural redundancy, introducing ε_s to measure approximation quality.
result The proposed method enhances SSL performance, as shown by theoretical and experimental validations.
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.
A new method reduces high-dimensional filtering to quadratic complexity.
problem High-dimensional dynamical systems inference and simulation.
method Low-rank Kalman filtering using dynamical low-rank integrator.
result The method reproduces exact Kalman filter in low-rank limit.
Review of algorithms for linear system approximations.
problem Linear approximation of high-dimensional dynamical systems.
method State-of-the-art algorithms for low-rank DMD.
result Provides additional details for comprehensive understanding.
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.
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.
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…
CALDERA compresses large language models by approximating weight matrices with low-rank, low-precision factors.
problem The large sizes of Large Language Models (LLMs) hinder deployment on edge devices.
method CALDERA approximates weight matrices W as Q+LR, where L and R are low-rank factors quantized to low precision. result CALDERA achieves better zero-shot performance than existing techniques, especially with low bit precision.
New method reduces summary points for datasets while maintaining quality.
problem Thinning datasets to reduce summary points while maintaining quality.
method Low-rank analysis of sub-Gaussian thinning.
result Guarantees high-quality compression for any distribution and kernel.
New method uses low logit rank to simplify complex language models.
problem Understanding and learning from modern language models.
method Exploiting the low logit rank structure of language models for efficient learning.
result An efficient algorithm for learning low logit rank models from queries.
PILNO uses neural operators to solve PDEs efficiently on point clouds.
problem Solving partial differential equations (PDEs) on point cloud data efficiently.
method Physics-informed low-rank neural operator framework combining low-rank kernel approximations and an encoder-decoder architecture.
result PILNO efficiently approximates solution operators of PDEs on point cloud data, satisfying PDE constraints and boundary conditions.
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…
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.