This talk will focus on some basic theories and algorithms of low-rank matrix recovery problems. Firstly, we give optimal RIP upper bound estimation and Null space equivalence characterization conditions, which involves several known conjectures. Furthermore, to study the case with robust sparse noise, we develop a unified framework of considering a non-smooth formulation with low-rank constraint for meeting the challenges of mixed noises—bounded noise and sparse noise. We show that the non-smooth formulations of the problems can be well solved by the projected sub-gradient methods at a rapid rate when initialized at any points. Finally, we discuss the stable recovery of the matrix that is simultaneously low-rank and Toeplitz, as a result, we resolve the conjecture by Chen et al.