The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime $ds/p \to \infty$, where $p$ denotes the signal dimension, $s$ the number of non-zero components of the signal, and $d$ the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order $s\log(p/s) / \log(ds/p)$, making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime $s=\alpha p$, $d=\psi p$, we prove that, for every fixed target error level $\delta$ and every slack $\varepsilon>0$, a sample size of order $p/\psi^2$ is sufficient for support recovery for arbitrarily small $\psi$.

한 줄 요약

이 연구는 희소 측정 행렬을 사용한 희소 신호의 support recovery에 대한 정보 이론적 한계와 trade-off를 분석한다.

핵심 기여도

희소 측정 행렬에서 support recovery가 가능한 최소 샘플 수에 대한 충분 조건을 제시 (Theorem 1).
측정 희소도 $d$와 신호 희소도 $s$에 따른 정보 이론적 임계치 $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log(p/s)/\log(ds/p)\right)$ 도출.
원래는 밀집 측정 행렬을 사용한 후 희소화한 경우에도 support recovery가 가능하다는 새로운 결과 제시 (Theorem 3).
희소화 강도 $\psi$에 따라 샘플 수 $n^{\text{Sp-ified}}_{\text{INF}} = \Theta(p/\psi^2)$가 필요하다는 수식적 분석.

핵심 아이디어

본 연구는 희소 측정 행렬을 사용할 때 발생하는 샘플 복잡도 증가와 희소화의 계산적 이점 사이의 trade-off를 정량적으로 분석한다. 기존 연구는 밀집 측정 행렬에서의 support recovery에 집중했으나, 본 연구는 측정 행렬 자체가 희소할 경우의 정보 이론적 한계를 탐구한다. 특히, 측정 행렬의 희소도 $d$가 증가함에 따라 샘플 수의 필요 조건이 $\log s / \log(ds/p)$ 비율로 증가한다는 점을 밝힘으로써, 희소 측정의 "가격"을 명확히 한다. 또한, 밀집 측정 행렬을 희소화한 경우에도 support recovery가 가능하다는 사실을 증명하며, $\psi$가 작을수록 샘플 수가 $1/\psi^2$ 비율로 증가해야 한다는 수식적 관계를 제시한다.

기술적 접근법

**측정 행렬**: 희소 가우시안 행렬 (각 행당 평균 $d$개의 비제로 성분).
**신호**: $s$-희소 이진 신호 ($\beta^\star \in \{0,1\}^p$).
**잡음 모델**: 가우시안 잡음 $Z \sim \mathcal{N}(0, \sigma^2 I_n)$.
**복원 알고리즘**: 최대우도 추정 (MLE).
**임계 조건**: $ds/p \to \infty$에서의 샘플 수 $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log(p/s)/\log(ds/p)\right)$.
**희소화된 밀집 행렬**: $s = \alpha p$, $d = \psi p$로 설정, 샘플 수 $n^{\text{Sp-ified}}_{\text{INF}} = \Theta(p/\psi^2)$.

주요 결과

**희소 측정 행렬**: $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log(p/s)/\log(ds/p)\right)$에서 support recovery 가능.
**희소화된 밀집 행렬**: $n^{\text{Sp-ified}}_{\text{INF}} = \Theta(p/\psi^2)$에서 support recovery 가능.
**비교**: 측정 희소도 $d$가 낮을수록 샘플 수가 $\log s / \log(ds/p)$ 비율로 증가.
**희소화 강도 $\psi$**: $\psi$가 작을수록 샘플 수가 $1/\psi^2$ 비율로 증가.

의의 및 한계

본 연구는 희소 측정 행렬을 사용할 때 발생하는 샘플 복잡도 증가와 희소화의 계산적 이점 사이의 trade-off를 정량적으로 분석함으로써, 희소 측정의 "가격"을 명확히 밝혔다. 이는 희소 측정 기반 압축 센싱, 신호 복원, 라디오 탐지 등 여러 분야에서 중요한 이론적 근거를 제공한다. 그러나 본 연구는 $d s / p \to \infty$ 조건 하에서만 성립하며, 더 극단적인 희소화 ($d s / p = o(1)$)에 대한 분석은 미비하다. 또한, 알고리즘적 복잡도나 다항 시간 복원 가능성에 대한 분석도 제한적이다.

실용적 활용

본 연구는 희소 측정 행렬을 사용하는 압축 센싱 시스템, MRI, 레이더, 디지털 통신 등에서 샘플링 복잡도와 측정 희소도의 trade-off를 설계할 때 유용한 이론적 기반을 제공한다. 특히, 희소화된 측정 행렬을 사용해 하드웨어 비용을 절감하면서도 신호 복원 성능을 유지하려는 시스템 설계에 적용 가능하다.