Rate-Optimal Subspace Estimation on Random Graphs Zhixin Zhou 1, Fan Zhou 2, Ping Li

Let ˆM be obtained from the last step of the algorithm, then by [16, Theorem 2.1], A This will be proved as follows. Since ˆM and M has at most rank r, rank(ˆM M) 2r. Then the proof is complete by applying (19). Firstly, we will prove (7). The proof is an application of Fano's inequality.