Weighed l1 on the simplex: Compressive sensing meets locality

• URL: http://arxiv.org/abs/2104.13894v2
• Date: Fri, 2 Aug 2024 05:05:48 GMT
• Title: Weighed l1 on the simplex: Compressive sensing meets locality
• Authors: Abiy Tasissa, Pranay Tankala, Demba Ba,
• Abstract summary: Sparse manifold learning algorithms combine techniques in manifold learning and sparse optimization to learn features that could be utilized for downstream tasks. Due to the intrinsic geometric structure of data, dictionary atoms might be redundant and do not satisfy the restricted isometry property or coherence condition. We discuss an optimization program that learns the dictionaries and sparse coefficients and demonstrate the utility of our regularization on synthetic and real datasets.
• Score: 4.47196217712431
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Sparse manifold learning algorithms combine techniques in manifold learning and sparse optimization to learn features that could be utilized for downstream tasks. The standard setting of compressive sensing can not be immediately applied to this setup. Due to the intrinsic geometric structure of data, dictionary atoms might be redundant and do not satisfy the restricted isometry property or coherence condition. In addition, manifold learning emphasizes learning local geometry which is not reflected in a standard $\ell_1$ minimization problem. We propose weighted $\ell_0$ and weighted $\ell_1$ metrics that encourage representation via neighborhood atoms suited for dictionary based manifold learning. Assuming that the data is generated from Delaunay triangulation, we show the equivalence of weighted $\ell_0$ and weighted $\ell_1$. We discuss an optimization program that learns the dictionaries and sparse coefficients and demonstrate the utility of our regularization on synthetic and real datasets.

Related papers

• Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
  We consider the problem of learning a graph modeling the statistical relations of the $d$ variables from a dataset with $n$ samples $X in mathbbRn times d$. We show that it is possible to estimate it from a sketch of size $m=Omegaleft((d+2k)log(d)right)$ where $k$ is the maximal number of edges of the underlying graph. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser.
  arXiv  Detail & Related papers  (2023-11-08T13:29:08Z)
• 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)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Dictionary Learning under Symmetries via Group Representations [1.304892050913381]
  We study the problem of learning a dictionary that is invariant under a pre-specified group of transformations. We apply our paradigm to investigate the dictionary learning problem for the groups SO(2) and SO(3).
  arXiv  Detail & Related papers  (2023-05-31T04:54:06Z)
• IAN: Iterated Adaptive Neighborhoods for manifold learning and dimensionality estimation [0.0]
  We introduce an algorithm for inferring adaptive neighborhoods for data given by a similarity kernel. A comparison against standard algorithms using, e.g., k-nearest neighbors, demonstrates their usefulness.
  arXiv  Detail & Related papers  (2022-08-19T02:15:08Z)
• Hyperbolic Vision Transformers: Combining Improvements in Metric Learning [116.13290702262248]
  We propose a new hyperbolic-based model for metric learning. At the core of our method is a vision transformer with output embeddings mapped to hyperbolic space. We evaluate the proposed model with six different formulations on four datasets.
  arXiv  Detail & Related papers  (2022-03-21T09:48:23Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  We propose a simple and practical tool $mathsfFriendlyCore$ that takes a set of points $cal D$ from an unrestricted (pseudo) metric space as input. When $cal D$ has effective diameter $r$, $mathsfFriendlyCore$ returns a "stable" subset $cal D_Gsubseteq cal D$ that includes all points. $mathsfFriendlyCore$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy
  arXiv  Detail & Related papers  (2021-10-19T17:43:50Z)
• 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)
• K-Deep Simplex: Deep Manifold Learning via Local Dictionaries [8.137198664755598]
  We propose K-Deep Simplex which learns a dictionary comprising synthetic landmarks, along with representation coefficients supported on a simplex. We solve the proposed optimization program using alternating minimization and design an efficient, interpretable autoencoder using algorithm unrolling. Experiments show that the algorithm is highly efficient and performs competitively on synthetic and real data sets.
  arXiv  Detail & Related papers  (2020-12-03T18:13:26Z)
• Parametric UMAP embeddings for representation and semi-supervised learning [0.03823356975862005]
  UMAP is a non-parametric graph-based dimensionality reduction algorithm to find low-dimensional embeddings of structured data. We show that Parametric UMAP performs comparably to its non-parametric counterpart while conferring the benefit of a learned parametric mapping. We then explore UMAP as a regularization, constraining the latent distribution of autoencoders, parametrically varying global structure preservation, and improving classifier accuracy for semi-supervised learning.
  arXiv  Detail & Related papers  (2020-09-27T23:45:00Z)
• Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies [60.285091454321055]
  We design a simple and efficient embedding algorithm that learns a small set of anchor embeddings and a sparse transformation matrix. On text classification, language modeling, and movie recommendation benchmarks, we show that ANT is particularly suitable for large vocabulary sizes.
  arXiv  Detail & Related papers  (2020-03-18T13:07:51Z)

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.