We study a data model in which the data matrix D can be expressed as D = L + S + C, where L is a low rank matrix, S an element-wise sparse matrix and C a matrix whose non-zero columns are outlying data points. To date, robust PCA algorithms have solely considered models with either S or C, but not both. As such, existi…
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,181 papers · 148 categories
Trend · papers per month
48 results for “Sparse corruptions”
Novel algorithm recovers sparse parameters in high-dimensional data with constant corruption.
problem Sparse regression with high dimensionality and constant fraction of corruptions.
method Robust Iterative Hard Thresholding, filtering algorithm for outlier removal.
result Near information-theoretically optimal error guarantee with sub-linear sample complexity.
New method for separating foreground from background in noisy, moving camera video.
problem Foreground-background separation in noisy, free-moving camera video.
method Registers frames, encodes perspective as missing data, uses OptShrink for low-rank estimation, and weighted total variation for smooth foreground.
result Panoramic background component that stitches together corrupted data from overlapping frames.
New methods tackle robust reinforcement learning in sparse, corrupted data.
problem Tackles robust reinforcement learning in sparse, corrupted data.
method Proposes actor-critic methods with sparse robust estimator oracles.
result First non-vacuous guarantees in high-dimensional sparse MDPs with single-policy concentrability coverage.
Robust Lasso-Zero handles missing covariates and sparse corruptions.
problem Sparse corruptions and missing covariates in sparse linear models.
method Extension of Lasso-Zero to handle sparse corruptions, with theoretical guarantees on sign recovery.
result Robust Lasso-Zero can handle missing values without specifying a parametric model.
Robustly estimates sparse data with corrupted outliers.
problem Adversarial corruption in high-dimensional sparse data.
method Iterative filtering using spectral techniques.
result Achieves near-optimal robustness guarantees.
New algorithm robustly estimates sparse models in high dimensions with corrupted data.
problem Estimating latent variable models with arbitrarily corrupted samples in high dimensional space.
method Trimmed (Gradient) Expectation Maximization with trimming gradients and hard thresholding steps.
result The algorithm converges to near optimal statistical rate geometrically under certain conditions.
We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corrup…
Paper tackles tensor completion from sparse corrupted data using convex optimization.
problem Estimating multidimensional arrays from a subset of corrupted entries.
method Solves a convex program that minimizes a weighted combination of tubal nuclear norm and -norm.
result Exact recovery of incoherent tensors with overwhelming probability.
Robust testing of sparse signals in corrupted data.
problem Testing the norm of high-dimensional sparse signals in the presence of arbitrary corruption.
method Two observation models: i.i.d. samples from and sparse linear regression model.
result The robust testing requires significantly more samples than non-robust testing.
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 …
Paper tackles robust -estimation for high-dimensional data with heavy tails or arbitrary corruption.
problem Sparsity-constrained -estimation with heavy-tailed or corrupted data.
method Defines Robust Descent Condition (RDC) and uses Robust Hard Thresholding (IHT) with gradient estimators.
result Robust Hard Thresholding is minimax optimal for -sparse high-dimensional linear and logistic regression with heavy tails or arbitrary corruption.
We consider the robust phase retrieval problem of recovering the unknown signal from the magnitude-only measurements, where the measurements can be contaminated by both sparse arbitrary corruption and bounded random noise. We propose a new nonconvex algorithm for robust phase retrieval, namely Robust Wirtinger Flow to …
New method estimates sparse mean from noisy data without knowing sparsity level.
problem Sparse mean estimation under adversarial corruptions.
method Incremental learning approach to nonconvex optimization.
result Achieves optimal statistical rate under moderate signal-to-noise ratio.
This paper examines a general class of noisy matrix completion tasks where the goal is to estimate a matrix from observations obtained at a subset of its entries, each of which is subject to random noise or corruption. Our specific focus is on settings where the matrix to be estimated is well-approximated by a product …
We consider high dimensional sparse regression, and develop strategies able to deal with arbitrary -- possibly, severe or coordinated -- errors in the covariance matrix . These may come from corrupted data, persistent experimental errors, or malicious respondents in surveys/recommender systems, etc. Such non-stochas…
New method improves deep learning models robustness to label noise.
problem Improving deep learning models' robustness to corrupted labels.
method Sparse over-parameterization and implicit regularization.
result State-of-the-art test accuracy against label noise on various datasets.
Improved data analysis with robust SPCA algorithm.
problem Identifying localized spatial structures and disambiguating time scales in low-rank data.
method Formulated as a value-function optimization problem, then extended with randomized linear algebra methods for scalability.
result Robust and efficient sparse principal components in corrupted data.
Efficiently recovers data corrupted by adversarial noise in structured settings.
problem Recovering clean data points from corrupted Gaussian data with low-rank noise and adversarial coordinate corruptions.
method Developed an efficient algorithm using a combinatorial approach to analyze Basis Pursuit (BP) method.
result Achieved nearly-optimal recovery of data points up to a error bound.
Paper tackles robust Euclidean distance estimation with sparse outliers.
problem Estimating point positions from corrupted distance measurements.
method Proposes a novel algorithm using Nyström method and robust PCA.
result Achieves accurate recovery with minimal anchors and sparse outliers.
New algorithm improves PPS for multi-object matching.
problem Efficiently synchronize partial permutations for multi-object matching.
method Proposed CEMP-Partial algorithm for partial permutation synchronization (PPS). Uses sparse matrix operations and nonconvex weighted projected power method.
result Proves CEMP-Partial can exactly classify corrupted and clean partial permutations under adversarial corruption.
DSF improves EEG model robustness to missing channels and noise.
problem Robust learning from corrupted EEG data with missing channels.
method Dynamic Spatial Filtering (DSF) as a multi-head attention module.
result DSF achieves up to 29.4% accuracy improvement over baseline models in noisy conditions.
We improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. 1) In compressed sensing, we show that if the m \times n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tr…
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.
Recovering low-rank and sparse matrices from incomplete or corrupted observations is an important problem in machine learning, statistics, bioinformatics, computer vision, as well as signal and image processing. In theory, this problem can be solved by the natural convex joint/mixed relaxations (i.e., l_{1}-norm and tr…
New method tackles tensor regression with robust Kaczmarz approach.
problem Reconstructing tensor signals from corrupted measurements.
method Quantile-based randomized Kaczmarz method for tensor linear systems.
result Improved convergence and robustness to adversarial corruptions.
Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterizationcs.LG
Gradient descent recovers low-rank matrices from corrupted measurements with double over-parameterization.
problem Robust recovery of low-rank matrices from grossly corrupted measurements.
method Gradient descent with discrepant learning rates for double over-parameterized models.
result Gradient descent with discrepant learning rates provably recovers the underlying matrix without prior knowledge on rank or sparsity.
High-dimensional data often lie in low-dimensional subspaces corresponding to different classes they belong to. Finding sparse representations of data points in a dictionary built using the collection of data helps to uncover low-dimensional subspaces and address problems such as clustering, classification, subset sele…
New algorithm separates sparse sources from Poisson measurements.
problem Blind source separation of sparse sources from Poisson measurements.
method pGMCA algorithm for Poisson measurements.
result Recovery of sparse sources from Poisson measurements.
New method for robust PCA with exponential family distributions.
problem Recovering low-rank structure from data matrices with outliers.
method Alternating Direction Method of Multipliers for .
result Demonstrated effectiveness in steel sheet defect detection and crime activity monitoring.
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.
New algorithm defends against adversarial examples in image classification.
problem Defending against adversarial examples in image classification.
method Approximates Discrete Fourier transform of sparse signals corrupted by noise.
result Successfully defends against adversaries in image classification.
Class selectivity affects robustness to corruptions but not to adversarial attacks.
problem Understanding the relationship between class selectivity and robustness in neural networks.
method Investigated the impact of class selectivity on robustness to natural corruptions and adversarial attacks using Tiny ImageNetC and CIFAR10C datasets.
result Decreasing class selectivity increases robustness to both natural corruptions and adversarial attacks.
Study robust recovery of low-rank matrices from corrupted measurements without rank prior.
problem Robust recovery of low-rank matrices from corrupted Gaussian measurements with unknown rank.
method Subgradient method with diminishing stepsizes for nonconvex nonsmooth problem.
result Subgradient method converges to exact low-rank solution at sublinear rate under RDPP condition.
New method for robust regression with near-optimal performance even with high corruption rates.
problem Robust linear regression with response variable corruptions.
method Adaptive hard thresholding for consistent estimation.
result Near-optimal consistent estimation of the true regression vector with fraction of corruptions.
Sparse linear regression with compressed and low-precision data via concave quadratic programmingmath.OC
New method recovers sparse vectors from compressed, noisy data.
problem Recovering sparse vectors from compressed and noisy measurements.
method Non-convex quadratic programming exploiting prior magnitude information.
result More efficient support recovery with sufficient conditions for success.
The performance of sparse signal recovery from noise corrupted, underdetermined measurements can be improved if both sparsity and correlation structure of signals are exploited. One typical correlation structure is the intra-block correlation in block sparse signals. To exploit this structure, a framework, called block…
New algorithms reduce communication for sparse mean estimation in noisy distributed systems.
problem Sparse normal means estimation with limited communication in a distributed setting.
method Two distributed algorithms for estimating a sparse mean vector with sublinear communication.
result Correct support of the sparse mean can be recovered with significantly less communication than previously required.
Robust GP model detects and corrects sparse outliers.
problem Non-Gaussian noise in real-world data.
method Relevance pursuit for data-point-specific noise levels.
result Strong concavity and approximation guarantees for subset selection.
Proposes a method to handle sparse multiway count data with false zeros using zero-truncated Poisson regression.
problem Handling sparse multiway count data corrupted by false zeros.
method Zero-truncated Poisson regression with tensor completion.
result Accurate estimation of multiway count data from approximately non-zero counts.
Kernel regression predicts graph signals in noisy environments.
problem Predicting smooth graph signals in the presence of sparse noise.
method Kernel regression with -norm and -norm optimization using IRLS.
result Efficacy demonstrated on real-world temperature data.
New algorithm learns PTFs with noisy data efficiently.
problem Learning low-degree PTFs with noisy data efficiently.
method Structural result and novel robust Chow vector estimation.
result PAC learns PTFs with nasty noise using efficient samples.
Novel algorithm for separating moving camera video into static and dynamic components.
problem Foreground-background separation in noisy, moving camera video.
method Augmented robust PCA with total variation regularization, OptShrink low-rank matrix estimator.
result Panoramic low-rank component spanning entire field of view, automatically stitching corrupted data.
New analysis enables inversion of deep generative models with unique solutions.
problem Inverting deep generative models like GANs and VAEs.
method Sparse representation theory and layer-wise inversion pursuit algorithms.
result Invertible solutions for generative models with unique latent vectors.
This paper solves tensor robust principal component analysis via scaled gradient descent.
problem Extracting useful information from tensor data robust to corruptions and ill-conditioning.
method Directly recovers low-rank tensor factors via scaled gradient descent with adaptive thresholding.
result The proposed algorithm converges linearly to the true low-rank tensor at a constant rate independent of the condition number.
Robust estimators for Gaussian sparse tasks with optimal error under contamination.
problem Robust mean estimation, PCA, and linear regression in the presence of Huber contamination.
method Novel multidimensional filtering method for sparse regime.
result Optimal error guarantees within constant factors for Gaussian robust -sparse mean estimation.
Koopman Regularizationmath.DS
Koopman Regularization learns governing equations from sparse data.
problem Learning governing equations from sparse and corrupted data.
method Constrained optimization using Koopman Eigenfunctions.
result Restores dynamics precisely with minimal assumptions.
A simple self-supervised model for tensor RPCA using deep unfolding.
problem Tensor robust principal component analysis (RPCA) challenges in practical applications.
method Deep unfolding with only four hyperparameters.
result Competitive or superior performance compared to supervised methods, even in data-starved scenarios.