Minimax rate of convergence and the performance of ERM in phase recovery

preprint2013arXivOpen access

Abstract

We study the performance of Empirical Risk Minimization in noisy phase retrieval problems, indexed by subsets of Rn\R^n and relative to subgaussian sampling; that is, when the given data is $y_i=\inr{a_i,x_0}^2+w_i$ for a subgaussian random vector aa, independent noise ww and a fixed but unknown x0x_0 that belongs to a given subset of Rn\R^n. We show that ERM produces x^\hat{x} whose Euclidean distance to either x0x_0 or −x0-x_0 depends on the gaussian mean-width of the indexing set and on the signal-to-noise ratio of the problem. The bound coincides with the one for linear regression when ∥x0∥2\|x_0\|_2 is of the order of a constant. In addition, we obtain a minimax lower bound for the problem and identify sets for which ERM is a minimax procedure. As examples, we study the class of dd-sparse vectors in Rn\R^n and the unit ball in ℓ1n\ell_1^n.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.