The paper presents novel techniques for analyzing the problem of low-rank matrix recovery, showing that an unknown $n \times n$ matrix of rank $r$ can be efficiently reconstructed from only $O(n r \nu \ln^2 n)$ randomly sampled expansion coefficients with respect to any given matrix basis. The number $\nu$ quantifies the "degree of incoherence" between the unknown matrix and the basis. The results improve upon existing methods, which primarily focused on matrix completion, and provide tighter bounds in some cases. The proof consists of a series of elementary steps, making it more accessible than previous highly involved methods. The paper also discusses operator bases that are incoherent to all low-rank matrices simultaneously, and shows that $O(n r \nu \ln n)$ randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The bound is tight up to multiplicative constants.The paper presents novel techniques for analyzing the problem of low-rank matrix recovery, showing that an unknown $n \times n$ matrix of rank $r$ can be efficiently reconstructed from only $O(n r \nu \ln^2 n)$ randomly sampled expansion coefficients with respect to any given matrix basis. The number $\nu$ quantifies the "degree of incoherence" between the unknown matrix and the basis. The results improve upon existing methods, which primarily focused on matrix completion, and provide tighter bounds in some cases. The proof consists of a series of elementary steps, making it more accessible than previous highly involved methods. The paper also discusses operator bases that are incoherent to all low-rank matrices simultaneously, and shows that $O(n r \nu \ln n)$ randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The bound is tight up to multiplicative constants.