Iterative Algorithm for Discrete Structure Recovery

摘要: We propose a general modeling and algorithmic framework for discrete structure recovery that can be applied to wide range of problems. Under this framework, we are able study the clustering labels, ranks players, signs regression coefficients, cyclic shifts, even group elements from unified perspective. A simple iterative algorithm is proposed recovery, which generalizes methods including Lloyd's power method. linear convergence result established in paper under appropriate abstract conditions on stochastic errors initialization. illustrate our theory by applying it several representative problems: (1) Gaussian mixture model, (2) approximate ranking, (3) sign compressed sensing, (4) multireference alignment, (5) synchronization, show minimax rate achieved each case.