Uncertainty Principles and Vector Quantization

Abstract

Given a frame in C^n which satisfies a form of the uncertainty principle (as introduced by Candes and Tao), it is shown how to quickly convert the frame representation of every vector into a more robust Kashin's representation whose coefficients all have the smallest possible dynamic range O(1/\sqrt{n}). The information tends to spread evenly among these coefficients. As a consequence, Kashin's representations have a great power for reduction of errors in their coefficients, including coefficient losses and distortions.

Final version, to appear in IEEE Trans. Information Theory. Introduction updated, minor inaccuracies corrected.

References in corpus (1)

• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

Cited by in corpus (15)

• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Coefficient Quantization for Frames in Banach Spaces
• Breaking the Communication-Privacy-Accuracy Trilemma
• Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
• Democratic Representations
• Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit
• Bayesian anti-sparse coding
• Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding
• Almost-Euclidean subspaces of ${\ell }_1^N$ via tensor products: a simple approach to randomness reduction
• ScionFL: Efficient and Robust Secure Quantized Aggregation
• DRIVE: One-bit Distributed Mean Estimation
• Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor
• Adaptive Federated Dropout: Improving Communication Efficiency and Generalization for Federated Learning
• Lossless Compression of Efficient Private Local Randomizers
• New insights for the multivariate square-root lasso