Analysis of low rank matrix recovery via Mendelson's small ball method

Kabanava, Maryia; Rauhut, Holger und Terstiege, Ulrich (2015): Analysis of low rank matrix recovery via Mendelson's small ball method. International Conference on Sampling Theory and Applications (SampTA), Washington, DC, 25-29 May 2015. In: 2015 International Conference on Sampling Theory and Applications (SampTA), IEEE. S. 387-391

Abstract

We study low rank matrix recovery from undersampled measurements via nuclear norm minimization. We aim to recover an n1 x n2 matrix X from m measurements (Frobenius inner products) 〈X, Aj〉, j = 1...m. We consider different scenarios of independent random measurement matrices Aj and derive bounds for the minimal number of measurements sufficient to uniformly recover any rank r matrix X with high probability. Our results are stable under passing to only approximately low rank matrices and under noise on the measurements. In the first scenario the entries of the Aj are independent mean zero random variables of variance 1 with bounded fourth moments. Then any X of rank at most r is stably recovered from m measurements with high probability provided that m ≥ Cr max{n1, n2}. The second scenario studies the physically important case of rank one measurements. Here, the matrix X to recover is Hermitian of size n × n and the measurement matrices Aj are of the form Aj = aja*j for some random vectors aj. If the aj are independent standard Gaussian random vectors, then we obtain uniform stable and robust rank-r recovery with high probability provided that m ≥ crn. Finally we consider the case that the aj are independently sampled from an (approximate) 4-design. Then we require m ≥ crn log n for uniform stable and robust rank-r recovery. In all cases, the results are shown via establishing a stable and robust version of the rank null space property. To this end, we employ Mendelson's small ball method.

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultät: Mathematik, Informatik und Statistik > Mathematik > Lehrstuhl für Mathematik der Informationsverarbeitung
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Sprache: Englisch