Unified framework for solving low-rank plus sparse matrix recovery problems.
problem Solving general low-rank plus sparse matrix recovery problems.
method Unified framework based on matrix factorization, projected gradient descent, and double thresholding operator.
result Our algorithm converges to the unknown low-rank and sparse matrices at a locally linear rate, matching robustness guarantees.
We consider the problem of modeling multivariate time series with parsimonious dynamical models which can be represented as sparse dynamic Bayesian networks with few latent nodes. This structure translates into a sparse plus low rank model. In this paper, we propose a Gaussian regression approach to identify such a mod…
Given the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, the goal of this paper is to establish deterministic conditions under which exact recovery of the low-rank and sparse components becomes possible. This fundamental identifiability issue arises with tra…
Unified framework HASSLE-free decomposes large model weights into sparse and low-rank components.
problem Efficiently compress large foundation models to reduce inference costs.
method Designs a unified framework for sparse plus low-rank matrix decomposition with a local layer-wise reconstruction error objective.
result HASSLE-free framework significantly outperforms state-of-the-art methods in compression and evaluation benchmarks.
New method decomposes corrupted data matrices into sparse and low-rank components.
problem Decomposing corrupted data matrices into sparse and low-rank components.
method Discrete optimization approach with alternating minimization, semidefinite relaxation, and branch-and-bound algorithm.
result High-quality solutions and meaningful bounds for SLR problems.
3BASiL-TM decomposes LLMs into sparse and low-rank matrices for efficient compression.
problem Efficiently compressing large language models without significant performance loss.
method 3-Block ADMM method and transformer-matching refinement step for sparse plus low-rank decomposition.
result 3BASiL-TM reduces perplexity gap by over 30% and speeds up compression by 2.5x.
New guarantees for recovering matrices as low-rank plus sparse from fewer measurements.
problem Recovering matrices as the sum of a low-rank and sparse matrix from a limited number of measurements.
method Developed guarantees for recovery of low-rank plus sparse matrices from O(r(m+n−r)+s)log(mn/s) measurements, using semidefinite programming and gradient descent algorithms. result Guarantees for recovery of low-rank plus sparse matrices from fewer measurements than previously possible.
A new method models user-specific parameters as a low-rank plus sparse component for efficient personalization.
problem Efficient personalization of machine learning models for individual users.
method Meta-learning approach that models network weights as a sum of low-rank and sparse components.
result The proposed method, AMHT-LRS, achieves nearly optimal sample complexity for estimating the low-rank and sparse components.
Paper proposes a new method to separate low rank and sparse matrices without bias.
problem Recovering low rank and sparse matrices from measurements.
method Uses nonconvex regularizers and alternating proximal gradient descent.
result Error bounds for the algorithm applied to sparse optimization, matrix completion, and robust PCA.
Efficient solver for nonconvex tensor regularization reduces computational cost.
problem Computational inefficiency in extending nonconvex regularization to tensor learning.
method Proximal average algorithm with adaptive momentum, maintaining sparse plus low-rank structure.
result Shows good statistical performance and accuracy on tensor completion problems.
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…
New algorithm speeds up LVGGM estimation by solving nonconvex optimization.
problem Estimating the latent variable Gaussian graphical model with sparse and low-rank components.
method Sparsity constrained maximum likelihood estimator with alternating gradient descent and hard thresholding.
result Our algorithm converges linearly to the optimal components up to statistical precision.
New method for factor analysis using nuclear and ℓ0 norms.
problem Finding a low-rank plus sparse decomposition from noisy covariance matrix.
method Formulated an optimization problem with nuclear norm, ℓ0 norm, and KL divergence. Used alternating minimization algorithm. result Algorithm effectively decomposes covariance matrices in synthetic and real datasets.
We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation X of the sum of an approximately) low rank matrix Θ⋆ with a second matrix Γ⋆ endowed with a complementary …
SILVar models latent variables in complex systems.
problem Estimating latent variables in complex, networked systems.
method Semi-parametric, non-linear regression model with regularized empirical risk minimization.
result Joint estimation of non-linearities, direct interactions, and unmodeled elements.
cuRegOT accelerates GPU-based entropic OT solving.
problem Slow convergence and high computational cost of optimal transport on GPUs.
method High-performance GPU solver with algorithmic and architectural optimizations.
result Significant speedups over state-of-the-art solvers.
Paper detects communities from graph signals using low-rank excitation modeling.
problem Detect communities in graphs from noisy signals.
method Model signals as graph filter outputs, apply spectral method to covariance matrix.
result Community structure can be retrieved directly from graph signals.
The paper tackles transfer learning for growing matrix representations, improving estimation accuracy.
problem Structured matrix estimation under growing ambient dimensions and latent representations.
method Proposes a general transfer framework decomposing target parameters into embedded source components, low-rank innovations, and sparse edits. Develops an anchored alternating projection estimator.
result Establishes deterministic error bounds that separate target noise, representation growth, and source estimation error, yielding improved rates.
Gaussian graphical models (GGM) have been widely used in many high-dimensional applications ranging from biological and financial data to recommender systems. Sparsity in GGM plays a central role both statistically and computationally. Unfortunately, real-world data often does not fit well to sparse graphical models. I…
Paper tackles matrix estimation under arbitrary noise, achieving minimax optimality.
problem Noisy low-rank-plus-sparse matrix recovery under arbitrary dependence.
method Incoherent-constrained least-square estimator, novel energy spreading result.
result Achieves minimax optimality in estimating structured Markov transition kernels.
This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natura…
Efficiently finds sparse solutions to max-plus equations for convex regression.
problem Finding sparse solutions to max-plus equations for convex multivariate regression.
method Polynomial-time algorithm for sparse approximate solutions.
result Optimal piecewise-linear fitting with minimum number of regions.
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.
Paper develops an online EM algorithm for graph signal inference from streaming data.
problem Joint inference and clustering of graph signals with non-white excitation.
method Mixture model with low-rank plus sparse prior, online EM algorithm.
result Proposed online EM algorithm converges to MAP solution.
RKPCA improves robustness of PCA for high-rank matrices.
problem Robust recovery of high-rank matrices corrupted by sparse noises.
method RKPCA decomposes matrices into sparse and low-rank components.
result RKPCA provides high recovery accuracy with theoretical guarantees.
Robust high-dimensional data processing has witnessed an exciting development in recent years, as theoretical results have shown that it is possible using convex programming to optimize data fit to a low-rank component plus a sparse outlier component. This problem is also known as Robust PCA, and it has found applicati…
Unified model for signed networks separates balance and anomaly effects.
problem Ignoring sign information in signed networks leads to inaccurate analysis.
method Low rank plus sparse matrix decomposition with regularized formulation.
result The model accurately detects communities and anomalies in signed networks.
New MCMC method learns sparse preconditioner for high-dimensional problems.
problem High-dimensional sampling with complex correlation structures.
method Adaptive MCMC with sparse preconditioner using online PCA.
result Significant reduction in computational complexity and improved performance.
Algorithm recovers sparse and low rank matrix components efficiently.
problem Recovery of sparse and low rank components of matrices.
method Iterative method with adaptive thresholding.
result Algorithm performs well with low run-time and suitable for non-sparse noise.
We consider the matrix completion problem of recovering a structured matrix from noisy and partial measurements. Recent works have proposed tractable estimators with strong statistical guarantees for the case where the underlying matrix is low--rank, and the measurements consist of a subset, either of the exact individ…
Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix completion, and principal components pursuit. This paper devel…
Survey on nonconvex penalties for sparse and low-rank recovery in various fields.
problem Achieving sparsity and low-rankness in signal processing, statistics, and machine learning.
method Analysis of nonconvex penalties and their applications.
result Nonconvex penalties can significantly improve performance in various applications.
New model captures time series dependence across and within blocks.
problem Complex multivariate time series dependence structures.
method Time series Gaussian chain graph models with directed and undirected edges.
result Consistent recovery of time series chain graph structure.
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.
New Max-Plus neural network exploits subgradient sparsity for efficient training.
problem Training Max-Plus neural networks is challenging due to dense subgradients.
method Proposes a sparse subgradient algorithm tailored to Max-Plus models.
result Achieves more efficient updates while retaining theoretical guarantees.
Improved GCNs for non-sparse graphs with low-rank filters.
problem Training and evaluation of GCNs on large non-sparse graphs is computationally expensive.
method Introduced low-rank filters and a reduced-order GCN architecture.
result Significant runtime acceleration and improved accuracy achieved.
Proposes a method to estimate sparse low-rank matrices from noisy data.
problem Estimating sparse low-rank matrices from noisy observations.
method Objective function with non-convex penalties, ADMM algorithm.
result Proposed method outperforms convex methods in estimating sparse low-rank matrices.
Paper proposes a method for estimating sparse and low-rank tensors from sketchings.
problem Estimating sparse and low-rank tensors from limited data.
method Two-stage non-convex implementation using sparse tensor decomposition and thresholded gradient descent.
result Exact and stable recovery of tensors in noisy and noiseless cases with high probability.
New nonconvex regularizers improve low-rank matrix recovery efficiency and accuracy.
problem Efficiently recover low-rank matrices from incomplete data.
method Factor group-sparse regularization, related to Schatten-p norms.
result Improved generalization error bounds for Schatten-p norms as p decreases.
New method improves robust low-rank matrix completion for computer vision.
problem Robust low-rank matrix completion for partially observed data.
method Formulated as a nonsmooth Riemannian optimization problem over Grassmann manifold, solved with an alternating manifold proximal gradient continuation method.
result Demonstrated advantages over existing approaches in background extraction from surveillance videos.
HERA improves PLL by integrating heterogeneous loss and sparse-low-rank regularization.
problem Learning from data with partial labels.
method Combines heterogeneous loss and sparse-low-rank regularization.
result Achieves superior performance on artificial and real-world data.
Improved Frank-Wolfe for sparse/low-rank problems.
problem Sparse/low-rank optimization problems.
method Primal-Dual Block Frank-Wolfe algorithm.
result Empirically outperforms state-of-the-art methods in classification tasks.
The article develops a method to learn sparse and low rank PARAFAC decomposition robust to noise.
problem Learning sparse and low rank PARAFAC decomposition for tensors with missing values.
method Bayesian model with elastic net regularization, efficient algorithms for large scale problems.
result The method finds true rank and sparse factor matrix robust to noise.
Proposes a model to relate a tensor feature to a univariate outcome using sparse and low-rank components.
problem Relating a univariate outcome to a feature tensor with sparse and low-rank components.
method Divide-and-conquer strategy, stagewise estimation procedure for unit-rank tensor regression.
result The stagewise solution paths converge to those of regularized regression as step size goes to zero.
RNNs solve modular addition tasks using low rank and sparse Fourier structures.
problem Solving modular addition tasks with recurrent neural networks.
method Identified low rank structures and sparse Fourier representations in RNN weights.
result RNNs robust to removing individual frequencies but degrade with more ablation.
Sparse LR-LSSVM improves kernel machine performance.
problem Improving kernel machine performance with controlled model size.
method Introduces LR-LSSVM with low rank kernels and a two-step optimization algorithm.
result Proposed algorithm's performance is comparable or superior to existing kernel machines.
Unified model for tensor completion using low-rank and sparse Tucker decomposition.
problem Estimating missing data from incomplete tensor measurements.
method Unified low-rank and sparse enhanced Tucker decomposition model with ADMM.
result Our model achieves higher recovery accuracy on various real-world data sets.
Paper proposes CLAIR for efficient LLM fine-tuning across clients.
problem Fine-tuning large language models (LLMs) efficiently and collaboratively.
method Federated LoRA fine-tuning with Collaborative Low-rank Alignment and Identifiable Recovery (CLAIR).
result CLAIR achieves better performance and contamination detection compared to local fine-tuning.