  The phase retrieval problem has garnered significant attention since the
development of the PhaseLift algorithm, which is a convex program that operates
in a lifted space of matrices. Because of the substantial computational cost
due to lifting, many approaches to phase retrieval have been developed,
including non-convex optimization algorithms which operate in the natural
parameter space, such as Wirtinger Flow. Very recently, a convex formulation
called PhaseMax has been discovered, and it has been proven to achieve phase
retrieval via linear programming in the natural parameter space under optimal
sample complexity. The current proofs of PhaseMax rely on statistical learning
theory or geometric probability theory. Here, we present a short and elementary
proof that PhaseMax exactly recovers real-valued vectors from random
measurements under optimal sample complexity. Our proof only relies on standard
probabilistic concentration and covering arguments, yielding a simpler and more
direct proof than those that require statistical learning theory, geometric
probability or the highly technical arguments for Wirtinger Flow-like
approaches.
