Spiked Covariance Estimation from Modulo-Reduced Measurements
share
Consider the rank-1 spiked model: X=√(ν)ξu+ Z, where ν is the spike intensity, u∈𝕊^k-1 is an unknown direction and ξ∼𝒩(0,1),Z∼𝒩(0,I). Motivated by recent advances in analog-to-digital conversion, we study the problem of recovering u∈𝕊^k-1 from n i.i.d. modulo-reduced measurements Y=[X]Δ, focusing on the high-dimensional regime (k≫ 1). We develop and analyze an algorithm that, for most directions u and ν=poly(k), estimates u to high accuracy using n=poly(k) measurements, provided that Δ≳√(log k). Up to constants, our algorithm accurately estimates u at the smallest possible Δ that allows (in an information-theoretic sense) to recover X from Y. A key step in our analysis involves estimating the probability that a line segment of length ≈√(ν) in a random direction u passes near a point in the lattice Δℤ^k. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.
READ FULL TEXT