Normalized iterative hard thresholding for matrix completion. (English) Zbl 1282.65043

Matrices of low rank can be uniquely determined from fewer linear measurements, or entries, than the total number of entries in the matrix. The authors propose an alternating projection algorithm which uses an adaptive step size calculated to be exact for a restricted subspace. The proposed method has near-optimal order recovery guarantees from dense measurement masks and average case performance superior in some respects to other matrix completion algorithms for dense measurement masks and entry measurements. The proposed algorithm is able to recover matrices from extremely close to the minimum number of measurements necessary.


65F10 Iterative numerical methods for linear systems
15A29 Inverse problems in linear algebra
15A83 Matrix completion problems
41A29 Approximation with constraints
Full Text: DOI Link