Spiked Covariance Estimation from Modulo-Reduced Measurements

Abstract

Consider the rank-1 spiked model: $\mathbf{X}=\sqrt{\nu }\xi \mathbf{u}+\mathbf{Z}$, where $\nu$ is the spike intensity, $\mathbf{u}\in {\mathbb{S}}^{\mathbf{k}-1}$ is an unknown direction and $\xi \sim \mathcal{N}(0,1),\mathbf{Z}\sim \mathcal{N}(0,\mathbf{I})$. Motivated by recent advances in analog-to-digital conversion, we study the problem of recovering $\mathbf{u}\in {\mathbb{S}}^{\mathbf{k}-1}$ from $n$ i.i.d. modulo-reduced measurements $\mathbf{Y}=[\mathbf{X}]\mathrm{mod}\mathbf{\Delta }$, focusing on the high-dimensional regime ($k\gg 1$). We develop and analyze an algorithm that, for most directions $\mathbf{u}$ and $\nu =\mathrm{poly}(k)$, estimates $\mathbf{u}$ to high accuracy using $n=\mathrm{poly}(k)$ measurements, provided that $\Delta \gtrsim \sqrt{\log k}$. Up to constants, our algorithm accurately estimates $\mathbf{u}$ at the smallest possible $\Delta$ that allows (in an information-theoretic sense) to recover $\mathbf{X}$ from $\mathbf{Y}$. A key step in our analysis involves estimating the probability that a line segment of length $\approx \sqrt{\nu }$ in a random direction $\mathbf{u}$ passes near a point in the lattice $\Delta {\mathbb{Z}}^k$. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.

AISTATS, 2022

References in corpus (1)

• Unlimited Sampling from Theory to Practice: Fourier-Prony Recovery and Prototype ADC