Spiked Covariance Estimation from Modulo-Reduced Measurements

Consider the rank-1 spiked model: bfX=√nuxi bfu+ bfZ, where nu is the spike intensity, bfu∈mathbbSk-1 is an unknown direction and xi~ N(0,1),bfZ~ N(bf0,bfI). Motivated by recent advances in analog-to-digital conversion, we study the problem of recovering bfu∈ mathbbSk-1 from n i.i.d. modulo-reduced measurements bfY=[bfX]mod Delta, focusing on the high-dimensional regime (kgg 1). We develop and analyze an algorithm that, for most directions bfu and nu=poly(k), estimates bfu to high accuracy using n=poly(k) measurements, provided that Deltagtrsim √log k. Up to constants, our algorithm accurately estimates bfu at the smallest possible Delta that allows (in an information-theoretic sense) to recover bfX from bfY. A key step in our analysis involves estimating the probability that a line segment of length ≈√nu in a random direction bfu passes near a point in the lattice Delta mathbbZk. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.