Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors

Technical Summary: Sharp Bounds for Non-Adaptive Randomized Approximation of High-Dimensional Noisy Vectors

Problem Statement
This paper investigates the complexity of approximating the embedding $\ell_p^m \hookrightarrow \ell_q^m$ for $2 \le p < q \le \infty$ using non-adaptive randomized algorithms. The setting involves a finite-dimensional vector space $\mathbb{R}^m$ where the dimension $m$ is significantly larger than the number of available linear functionals $n$ (i.e., $n \ll m$). The goal is to recover a vector $x$ from the unit ball of $\ell_p^m$ using $n$ arbitrary linear measurements, minimizing the worst-case expected error in the $\ell_q$-norm.

The authors focus on the regime where $p \ge 2$, characterizing vectors in the unit ball of $\ell_p^m$ as "noisy vectors." In this context, randomized algorithms aim to recover the largest entries of $x$, while smaller entries act as noise scaling with the $\ell_2$-norm. For $p > 2$, the $\ell_2$-norm of a unit $\ell_p$-vector can be as large as $m^{1/2 - 1/p}$, creating a significant challenge for approximation.

Methodology
The paper employs Bakhvalov's trick (also known as Yao's principle) to establish lower bounds for randomized algorithms. This technique involves switching from a randomized setting to an average-case setting for deterministic algorithms. The core methodological steps include:

1. Construction of a Truncated Gaussian Mixture: The authors define a specific probability measure $\mu$ supported on the $\ell_p$-unit ball. This measure is constructed as a mixture of Gaussian distributions centered at specific sparse vectors $u_I$.

   • The centers $u_I$ are derived from a set $W$ of $k$-sparse vectors with entries in $\{-1, 0, 1\}$.
   • A random index $I$ selects a center, and Gaussian noise $\sigma Z_m$ is added.
   • The measure is truncated to ensure support within the $\ell_p$-unit ball, with the truncation probability shown to vanish as $m \to \infty$.

2. Reduction to a Packing Problem: The lower bound proof reduces the approximation problem to the task of identifying the correct center $u_I$ from noisy linear observations.

   • The linear information mapping is represented by a matrix $N$.
   • The observation $Y = N(X)$ becomes a Gaussian mixture centered at $v_I = N u_I$ with additive Gaussian noise.
   • The proof utilizes coding theory results (specifically Gilbert-Varshamov bounds) to construct a set of centers with sufficient $\ell_p$-separation, ensuring that the number of centers $M$ is large relative to the "packing number" $K$ (the maximum number of centers that can be confused within an $\epsilon$-ball).

3. Geometric Analysis of Super-Level Sets: The authors analyze the probability of large reconstruction errors by examining the super-level sets of the Gaussian mixture density. They demonstrate that if the number of measurements $n$ is too small relative to $m$ and the sparsity $k$, the reconstruction mapping cannot distinguish between the centers with high probability, leading to a lower bound on the average error.

Key Contributions and Results
The primary contribution of this work is the proof of matching lower bounds for the non-adaptive randomized approximation error, thereby establishing sharp bounds for the problem.

• Error Rate: For $2 \le p < q \le \infty$, the $n$-th minimal randomized error is shown to satisfy:
  $$e_{n}^{\text{ran, nonada}}(n, \ell_p^m \to \ell_q^m) \asymp \min \left\{ 1, \left( \frac{m^{1-2/p} \cdot \log m}{n} \right)^{\frac{1}{2}(1 - p/q)} \right\}$$
  This result matches previously known upper bounds obtained via denoising linear randomized algorithms (from [6, Thm 4.4]).

• Complexity: The dual notion of $\epsilon$-complexity (the number of measurements required to achieve error $\epsilon$) is derived as:
  $$n^{\text{ran, nonada}}(\epsilon, \ell_p^m \to \ell_q^m) \asymp \epsilon^{-2p/(1/p - 1/q)} \cdot m^{1-2/p} \cdot \log m$$

• Dependence on Dimension: The results highlight a polynomial dependence on the dimension $m$ (specifically $m^{1-2/p}$) for $p > 2$. This contrasts with the $p \in [1, 2]$ regime, where the dependence on $m$ is only logarithmic. The paper notes that the factor $m^{1-2/p}$ is unavoidable for non-adaptive algorithms due to the "noise" inherent in the $\ell_2$-norm of sparse vectors in high dimensions.

Significance and Scope
The paper claims to resolve the complexity of non-adaptive randomized approximation for the specific parameter range $2 \le p < q \le \infty$ by proving that the known upper bounds are asymptotically optimal.

• Comparison to Prior Work: Previous lower bounds (e.g., by Heinrich) were independent of $m$ and applied to the full range $1 \le p < q \le \infty$ but were not sharp for $p > 2$ in the high-dimensional regime. This paper provides the first lower bounds with the correct joint dependence on $n$ and $m$ for $p \ge 2$.
• Limitations: The authors explicitly state that the lower bounds are restricted to non-adaptive algorithms and the range $p \ge 2$.
  • For $p < 2$, the suitable average-case setting appears more difficult to analyze.
  • For adaptive algorithms, the complexity is known to be lower (involving $\log \log m$ instead of $\log m$), but proving lower bounds for the adaptive setting remains an open challenge, particularly for $p < 2$.
• Future Directions: The authors suggest that the Gaussian mixture technique used here could potentially be extended to adaptive randomized methods for $p \ge 2$ using information-theoretic techniques. They also propose that a more complex Gaussian measure involving random projections might be necessary to tackle the $1 \le p < 2$ case.

In summary, the paper provides a rigorous theoretical foundation for the difficulty of approximating high-dimensional vectors in $\ell_p$ spaces when $p \ge 2$ using non-adaptive randomized measurements, confirming that the cost of approximation scales polynomially with the dimension.