Representation and coding of signal geometry
From MaRDI portal
Publication:4603712
DOI10.1093/IMAIAI/IAX002zbMATH Open1386.94021arXiv1512.07636OpenAlexW2963591649MaRDI QIDQ4603712FDOQ4603712
Authors: Shantanu Rane, Hassan Mansour, Petros T. Boufounos 
Publication date: 19 February 2018
Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)
Abstract: Approaches to signal representation and coding theory have traditionally focused on how to best represent signals using parsimonious representations that incur the lowest possible distortion. Classical examples include linear and non-linear approximations, sparse representations, and rate-distortion theory. Very often, however, the goal of processing is to extract specific information from the signal, and the distortion should be measured on the extracted information. The corresponding representation should, therefore, represent that information as parsimoniously as possible, without necessarily accurately representing the signal itself. In this paper, we examine the problem of encoding signals such that sufficient information is preserved about their pairwise distances and their inner products. For that goal, we consider randomized embeddings as an encoding mechanism and provide a framework to analyze their performance. We also demonstrate that it is possible to design the embedding such that it represents different ranges of distances with different precision. These embeddings also allow the computation of kernel inner products with control on their inner product-preserving properties. Our results provide a broad framework to design and analyze embeddins, and generalize existing results in this area, such as random Fourier kernels and universal embeddings.
Full work available at URL: https://arxiv.org/abs/1512.07636
Recommendations
- Fast binary embeddings and quantized compressed sensing with structured matrices
- scientific article; zbMATH DE number 6999914
- Time for dithering: fast and quantized random embeddings via the restricted isometry property
- Random projections of smooth manifolds
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
dimensionality reductionkernel methodsquantizationrandomized embeddingscoding for inferencedistance representations
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Stable signal recovery from incomplete and inaccurate measurements
- A simple proof of the restricted isometry property for random matrices
- Compressed sensing
- Title not available (Why is that?)
- Random projections of smooth manifolds
- The geometry of graphs and some of its algorithmic applications
- On the impossibility of dimension reduction in l 1
- Dimensionality reduction with subgaussian matrices: a unified theory
- Title not available (Why is that?)
- The restricted isometry property and its implications for compressed sensing
- Problems and results in extremal combinatorics. I.
- One-bit compressed sensing by linear programming
- Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
- Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Locality-sensitive hashing scheme based on p-stable distributions
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Model-Based Compressive Sensing
- Robust Recovery of Signals From a Structured Union of Subspaces
- Democracy in action: quantization, saturation, and compressive sensing
- Coding for computing
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- New analysis of manifold embeddings and signal recovery from compressive measurements
- Toward a unified theory of sparse dimensionality reduction in Euclidean space
- Dimension reduction by random hyperplane tessellations
- Low distortion embeddings for edit distance
- NuMax: A Convex Approach for Learning Near-Isometric Linear Embeddings
- Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
- Title not available (Why is that?)
- Universal Rate-Efficient Scalar Quantization
- Sparse recovery from saturated measurements
- Stabilizing Nonuniformly Quantized Compressed Sensing With Scalar Companders
- A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
- Functional Compression Through Graph Coloring
- Distributed Scalar Quantization for Computing: High-Resolution Analysis and Extensions
Cited In (4)
Uses Software
This page was built for publication: Representation and coding of signal geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603712)
