  The purpose of this thesis is to develop new theories on high-dimensional
structured signal recovery under a rather weak assumption on the measurements
that only a finite number of moments exists. High-dimensional recovery has been
one of the emerging topics in the last decade partly due to the celebrated work
of Candes, Romberg and Tao (e.g. [CRT06, CRT04]). The original analysis there
(and the works thereafter) necessitates a strong concentration argument
(namely, the restricted isometry property), which only holds for a rather
restricted class of measurements with light-tailed distributions. It had long
been conjectured that high-dimensional recovery is possible even if restricted
isometry type conditions do not hold, but the general theory was beyond the
grasp until very recently, when the works [Men14a, KM15] propose a new
small-ball method. In these two papers, the authors initiated a new analysis
framework for general empirical risk minimization (ERM) problems with respect
to the square loss, which is robust and can potentially allow heavy-tailed loss
functions. The materials in this thesis are partly inspired by [Men14a], but
are of a different mindset: rather than directly analyzing the existing ERMs
for signal recovery for which it is difficult to avoid strong moment
assumptions, we show that, in many circumstances, by carefully re-designing the
ERMs to start with, one can still achieve the minimax optimal statistical rate
of signal recovery with very high probability under much weaker assumptions
than existing works.
