Dictionary Learning for the Almost-Linear Sparsity Regime
- URL: http://arxiv.org/abs/2210.10855v2
- Date: Mon, 27 Mar 2023 21:28:27 GMT
- Title: Dictionary Learning for the Almost-Linear Sparsity Regime
- Authors: Alexei Novikov and Stephen White
- Abstract summary: Dictionary learning is of increasing importance to applications in signal processing and data science.
We introduce SPORADIC (SPectral ORAcle DICtionary Learning), an efficient spectral method on family of reweighted covariance matrices.
We prove that in high enough dimensions, SPORADIC can recover overcomplete ($K > M$) dictionaries satisfying the well-known restricted isometry property (RIP)
These accuracy guarantees have an oracle property" that the support and signs of unknown sparse vectors $mathbfx_i$ can be recovered exactly with high probability, allowing for arbitrarily close
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Dictionary learning, the problem of recovering a sparsely used matrix
$\mathbf{D} \in \mathbb{R}^{M \times K}$ and $N$ $s$-sparse vectors
$\mathbf{x}_i \in \mathbb{R}^{K}$ from samples of the form $\mathbf{y}_i =
\mathbf{D}\mathbf{x}_i$, is of increasing importance to applications in signal
processing and data science. When the dictionary is known, recovery of
$\mathbf{x}_i$ is possible even for sparsity linear in dimension $M$, yet to
date, the only algorithms which provably succeed in the linear sparsity regime
are Riemannian trust-region methods, which are limited to orthogonal
dictionaries, and methods based on the sum-of-squares hierarchy, which requires
super-polynomial time in order to obtain an error which decays in $M$. In this
work, we introduce SPORADIC (SPectral ORAcle DICtionary Learning), an efficient
spectral method on family of reweighted covariance matrices. We prove that in
high enough dimensions, SPORADIC can recover overcomplete ($K > M$)
dictionaries satisfying the well-known restricted isometry property (RIP) even
when sparsity is linear in dimension up to logarithmic factors. Moreover, these
accuracy guarantees have an ``oracle property" that the support and signs of
the unknown sparse vectors $\mathbf{x}_i$ can be recovered exactly with high
probability, allowing for arbitrarily close estimation of $\mathbf{D}$ with
enough samples in polynomial time. To the author's knowledge, SPORADIC is the
first polynomial-time algorithm which provably enjoys such convergence
guarantees for overcomplete RIP matrices in the near-linear sparsity regime.
Related papers
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
We show that consistent recovery of the parameter vector in a robust linear regression model is information-theoretically impossible.
We show that it is possible to efficiently certify whether a given $n$-by-$d$ matrix is well-spread if the number of observations is quadratic in the ambient dimension.
arXiv Detail & Related papers (2022-06-16T11:17:44Z) - Semi-Random Sparse Recovery in Nearly-Linear Time [37.61139884826181]
We investigate the brittleness of fast sparse recovery algorithms to generative model changes.
Our approach differs from prior fast iterative methods with provable guarantees under semi-random generative models.
We design a new iterative method tailored to the geometry of sparse recovery which is provably robust to our semi-random model.
arXiv Detail & Related papers (2022-03-08T10:56:46Z) - On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary [0.4125187280299246]
We consider the probability that a random matrix $A in mathbbRm times N$ will serve as a bi-Lipschitz function $A: mathcalM rightarrow mathbbRm$ with bi-Lipschitz constants close to one.
We present a new class of highly structured distributions for embedding sufficiently low-dimensional submanifolds of $mathbbRN$.
arXiv Detail & Related papers (2021-10-08T15:27:52Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm.
Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises.
We complement the theory with an empirical evaluation across known difficult exploration tasks.
arXiv Detail & Related papers (2021-06-15T02:23:07Z) - Multiscale regression on unknown manifolds [13.752772802705978]
We construct low-dimensional coordinates on $mathcalM$ at multiple scales and perform multiscale regression by local fitting.
We analyze the generalization error of our method by proving finite sample bounds in high probability on rich classes of priors.
Our algorithm has quasilinear complexity in the sample size, with constants linear in $D$ and exponential in $d$.
arXiv Detail & Related papers (2021-01-13T15:14:31Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
We study the fundamental task of list-decodable mean estimation in high dimensions.
Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset.
A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
arXiv Detail & Related papers (2020-11-19T17:21:37Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples.
We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
arXiv Detail & Related papers (2020-09-30T19:10:32Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$
We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
arXiv Detail & Related papers (2020-07-16T06:44:44Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.