Guarantees of Fast Band Restricted Thresholding Algorithm for Low-Rank Matrix Recovery Problem

Abstract EN

Affine matrix rank minimization problem is a famous problem with a wide range of application backgrounds.

This problem is a combinatorial problem and deemed to be NP-hard.

In this paper, we propose a family of fast band restricted thresholding (FBRT) algorithms for low rank matrix recovery from a small number of linear measurements.

Characterized via restricted isometry constant, we elaborate the theoretical guarantees in both noise-free and noisy cases.

Two thresholding operators are discussed and numerical demonstrations show that FBRT algorithms have better performances than some state-of-the-art methods.

Particularly, the running time of FBRT algorithms is much faster than the commonly singular value thresholding algorithms.