Matrix recipes for hard thresholding methods (Q2251217)

This paper deals with a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. The authors present new strategies and review existing ones for hard thresholding methods to recover low-rank matrices from dimensionality reducing, linear projections. The discussion revolves around four basic building blocks that exploit the problem structure to reduce computational complexity without sacrificing stability. The complexity analysis of the proposed algorithms is provided. Two acceleration schemes are considered. The authors improve the convergence speed by exploiting randomized low rank projections and provide empirical support for their claims through experimental results on synthetic and real data.