Iterative Algorithm for Discrete Structure Recovery
We propose a general modeling and algorithmic framework for discrete structure recovery that can be applied to a wide range of problems. Under this framework, we are able to study the recovery of clustering labels, ranks of players, signs of regression coefficients, cyclic shifts, and even group elements from a unified perspective. A simple iterative algorithm is proposed for discrete structure recovery, which generalizes methods including Lloyd's algorithm and the power method. A linear convergence result for the proposed algorithm is established in this paper under appropriate abstract conditions on stochastic errors and initialization. We illustrate our general theory by applying it on several representative problems: (1) clustering in Gaussian mixture model, (2) approximate ranking, (3) sign recovery in compressed sensing, (4) multireference alignment, and (5) group synchronization, and show that minimax rate is achieved in each case.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringcompressed sensingSimilar Papers 제목 키워드 기반
Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning
We present FLOP (Fast Learning of Order and Parents), a score-based causal discovery algorithm for linear models. It pairs fast parent selection with iterative Cholesky-based score updates, cutting run-times over prior a…
Gradient-Based Learning of Discrete Structured Measurement Operators for Signal Recovery
Countless signal processing applications include the reconstruction of signals from few indirect linear measurements. The design of effective measurement operators is typically constrained by the underlying hardware and …
Rolling Shutter CorrectionRecovery of Noisy Points on Band-limited Surfaces: Kernel Methods Re-explained
We introduce a continuous domain framework for the recovery of points on a surface in high dimensional space, represented as the zero-level set of a bandlimited function. We show that the exponential maps of the points o…
Learning Structured Sparse Matrices for Signal Recovery via Unrolled Optimization
Countless signal processing applications include the reconstruction of an unknown signal from very few indirect linear measurements. Because the measurement operator is commonly constrained by the hardware or the physics…
compressed sensingRolling Shutter CorrectionCover Tree Compressed Sensing for Fast MR Fingerprint Recovery
We adopt data structure in the form of cover trees and iteratively apply approximate nearest neighbour (ANN) searches for fast compressed sensing reconstruction of signals living on discrete smooth manifolds. Levering on…
compressed sensingMagnetic Resonance FingerprintingQuantitative MRI