Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
  We study the role of the constraint set in determining the solution to
low-rank, positive semidefinite (PSD) matrix sensing problems. The setting we
consider involves rank-one sensing matrices: In particular, given a set of
rank-one projections of an approximately low-rank PSD matrix, we characterize
the radius of the set of PSD matrices that satisfy the measurements. This
result yields a sampling rate to guarantee singleton solution sets when the
true matrix is exactly low-rank, such that the choice of the objective function
or the algorithm to be used is inconsequential in its recovery. We discuss
applications of this contribution and compare it to recent literature regarding
implicit regularization for similar problems. We demonstrate practical
implications of this result by applying conic projection methods for PSD matrix
recovery without incorporating low-rank regularization.
