Uncertainty Principles and Vector Quantization

By Yurii Lyubarskii, Roman Vershynin. 2006

104 citations recorded by the source corpus.

Given a frame in Cn 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/ √(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.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Information Theory

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “[26] shows that if N > (1 + μ) d for some μ > 0, then there exists a tight frame [u1, .”
Federated Learning with Autotuned Communication-Efficient Secure Aggregation (2019, methodology): “We note that logarithmic dependence on d in the above MSE bound can be replaced with a constant [4], by appropriate use of Kashin’s representation [5].”
Expanding the Reach of Federated Learning by Reducing Client Resource Requirements (2018, methodology): “Basis transform Previous work [Lyubarskii and Vershynin, 2010, Koneˇcný et al., 2016b] has explored the idea of using a basis transform to reduce the error that will later be incurred by perturbations such as quantization.”
Coefficient quantization for frames in Banach spaces (2007, unknown): “ qn ≥ 1 + 2C δ N ≥ Vol(P(QN)) Vol(T(BX)) ≥ √ nα g(C 2(X))cK n . Taking the nth root on both sides yields our claim. Remark 5.13. In section 6 we will recall a result of Lyubarski and Vershinin [LV] which shows that for q > 1 there are ε < 1 , δ < 1, C < ∞ so that for any n ∈ Nand there”
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit (2007, unknown): “ately an orthonormal system. One can interpret the Restricted Isometry Condition as an abstract version of the Uniform Uncertainty Principle in harmonic analysis ([4], see also discussions in [3] and [16]). Theorem 1.2 (Sparse recovery under RIC [5]). Assume that the measurement matrix Φ satisﬁes th”
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor (2020, unknown): “In this section we introduce the notion of Kashin’s representation, the algorithm of Lyubarskii & Vershynin (2010) on computing it eﬃciently and then describe the quantization step.”
Signal representations with minimum ℓ∞-norm (2012, methodology): “The existence of such signal representations and matrices can either be shown via results obtained by Kashin [13], Garnaev and Gluskin [14], or by analyzing the outcome of the iterative algorithm proposed in [1], which computes signal representations with small `∞norm.”
Spread representations (2011, background): “To take care ofv ∈ ∂‖x‖∞, we partition the optimalx into x̄ its q middle-components associated with̄v = 0 andx̄ the remaining components that are equal to± x∞ associated with̄v.”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “This approach is based on Kashin’s representation that maps vectors in the unit d-dimensional ball to vectors in [−1, 1]O(d) (Lyubarskii & Vershynin, 2010).”