Universität zu Köln

Kabanava, Maryia ORCID: 0000-0002-5248-2617, Kueng, Richard, Rauhut, Holger and Terstiege, Ulrich (2016). Stable low-rank matrix recovery via null space properties. Inf. Inference, 5 (4). S. 405 - 442. OXFORD: OXFORD UNIV PRESS. ISSN 2049-8772

Full text not available from this repository.

Abstract

The problem of recovering a matrix of low rank from an incomplete and possibly noisy set of linear measurements arises in a number of areas. In order to derive rigorous recovery results, the measurement map is usually modelled probabilistically. We derive sufficient conditions on the minimal amount of measurements ensuring recovery via convex optimization. We establish our results via certain properties of the null space of the measurement map. In the setting where the measurements are realized as Frobenius inner products with independent standard Gaussian random matrices, we show that 10r(n(1) + n(2)) measurements are enough to uniformly and stably recover an n(1) x n(2) matrix of rank at most r. We then significantly generalize this result by only requiring independent mean zero, variance one entries with four finite moments at the cost of replacing 10 by some universal constant. We also study the case of recovering Hermitian rank-r matrices from measurement matrices proportional to rank-one projectors. For m >= Crn rank-one projective measurements onto independent standard Gaussian vectors, we show that nuclear norm minimization uniformly and stably reconstructs Hermitian rank-r matrices with high probability. Next, we partially de-randomize this by establishing an analogous statement for projectors onto independent elements of a complex projective 4-designs at the cost of a slightly higher sampling rate m >= Crn log n. Moreover, if the Hermitian matrix to be recovered is known to be positive semidefinite, then we show that the nuclear norm minimization approach may be replaced by minimizing the l(q)-norm of the residual subject to the positive semidefinite constraint (e.g. by a positive semidefinite least squares problem). Then no estimate of the noise level is required a priori. We discuss applications in quantum physics and the phase retrieval problem.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Kabanava, Maryia UNSPECIFIED orcid.org/0000-0002-5248-2617 UNSPECIFIED Kueng, Richard UNSPECIFIED UNSPECIFIED UNSPECIFIED Rauhut, Holger UNSPECIFIED UNSPECIFIED UNSPECIFIED Terstiege, Ulrich UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-253776
DOI:	10.1093/imaiai/iaw014
Journal or Publication Title:	Inf. Inference
Volume:	5
Number:	4
Page Range:	S. 405 - 442
Date:	2016
Publisher:	OXFORD UNIV PRESS
Place of Publication:	OXFORD
ISSN:	2049-8772
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language CONVEX; SIGNAL Multiple languages Computer Science, Artificial Intelligence; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/25377