A unified framework for linear dimensionality reduction in L1

DOI10.1007/S00025-015-0475-XMaRDI QIDQ310869zbMATH OpenOpenAlexFDO

Authors Felix Krahmer, Rachel Ward

Publication date 8 September 2016

Published in Results in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.1332

zbMATH Keywords

interpolation norm, random variablelinear dimensionality reduction

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Probabilistic methods in Banach space theory (46B09) Interpolation between normed linear spaces (46B70)

Abstract: For a family of interpolation norms $|cdot{|}_{1,2,s}$ on $mathbb{R}^n$, we provide a distribution over random matrices $Ph{i}_{s}inmathbb{R}^{mimesn}$ parametrized by sparsity level $s$ such that for a fixed set $X$ of $K$ points in $mathbb{R}^n$, if $mgeqCslog(K)$ then with high probability, $frac12|x{|}_{1,2,s}leq|Ph{i}_s(x){|}_{1}leq2|x{|}_{1,2,s}$ for all $xinX$. Several existing results in the literature reduce to special cases of this result at different values of $s$: for $s=n$, $|x{|}_{1,2,n}equiv|x{|}_1$ and we recover that dimension reducing linear maps can preserve the $el{l}_1$-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For $s=1$, $|x{|}_{1,2,1}equiv|x{|}_2$, and we recover an $el{l}_2/el{l}_1$ variant of the Johnson-Lindenstrauss Lemma for Gaussian random matrices. Finally, if $x$ is $s$-sparse, then $|x{|}_{1,2,s}=|x{|}_1$ and we recover that $s$-sparse vectors in $el{l}_1^n$ embed into $el{l}_1^{mathcalO(slog(n))}$ via sparse random matrix constructions.

Review text

For a family of interpolation norms \(\|\cdot \|_{1,2,s}\) on \(\mathbb{R}^n\) the authors provide a distribution over random matrices \(\Phi_s\in\mathbb{R}^{m\times n}\) parametrized by sparsity level \(s\) such that for a fixed set \(X\) of K points in \(\mathbb{R}^n\) holds: if \(m\geq Cs\log (K)\) then with high probability \(\frac12 \| x\|_{1,2,s}\leq \|\Phi_s(x)\|_1\leq 2\| x\|_{1,2,s}\) for all \(x\in X\). In this way, they manage to recove some existiong results in the literature (for \(s=n\), \(s=1\)).

Recommendations

• Sparser Johnson-Lindenstrauss transforms
• Sparsity lower bounds for dimensionality reducing maps
• Linear dimension reduction approximately preserving a function of the $1$-norm
• On variants of the Johnson–Lindenstrauss lemma

Cites work

• A mathematical introduction to compressive sensing
• A simple proof of the restricted isometry property for random matrices
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Compressed sensing with coherent and redundant dictionaries
• Compressed Sensing With Cross Validation
• Extensions of Lipschitz mappings into a Hilbert space
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• scientific article; zbMATH DE number 5764869 (Why is no real title available?)
• scientific article; zbMATH DE number 3944477 (Why is no real title available?)
• scientific article; zbMATH DE number 192914 (Why is no real title available?)
• Interpolation of Quasi-Normed Spaces.
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• New Bounds for Restricted Isometry Constants
• On the exact space complexity of sketching and streaming small norms
• One-bit compressed sensing by linear programming
• Probability and Computing
• Randomized algorithms for the low-rank approximation of matrices
• Smallest singular value of random matrices and geometry of random polytopes
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
• The best constants in the Khintchine inequality
• The Distribution of Rademacher Sums
• Tight embedding of subspaces of 𝐿_{𝑝} in ℓ_{𝑝}ⁿ for even 𝑝
• Tutorial on large deviations for the binomial distribution

Cited in

(7)

• A unified approach to sufficient dimension reduction
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Linear dimension reduction approximately preserving a function of the $1$-norm
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Persistent homology for low-complexity models
• Bilinear Lanczos components for fast dimensionality reduction and feature extraction

This page was built for publication: A unified framework for linear dimensionality reduction in L1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q310869)