Enhancing Pure-Pixel Identification Performance via Preconditioning
  In this paper, we analyze different preconditionings designed to enhance
robustness of pure-pixel search algorithms, which are used for blind
hyperspectral unmixing and which are equivalent to near-separable nonnegative
matrix factorization algorithms. Our analysis focuses on the successive
projection algorithm (SPA), a simple, efficient and provably robust algorithm
in the pure-pixel algorithm class. Recently, a provably robust preconditioning
was proposed by Gillis and Vavasis (arXiv:1310.2273) which requires the
resolution of a semidefinite program (SDP) to find a data points-enclosing
minimum volume ellipsoid. Since solving the SDP in high precisions can be time
consuming, we generalize the robustness analysis to approximate solutions of
the SDP, that is, solutions whose objective function values are some
multiplicative factors away from the optimal value. It is shown that a high
accuracy solution is not crucial for robustness, which paves the way for faster
preconditionings (e.g., based on first-order optimization methods). This first
contribution also allows us to provide a robustness analysis for two other
preconditionings. The first one is pre-whitening, which can be interpreted as
an optimal solution of the same SDP with additional constraints. We analyze
robustness of pre-whitening which allows us to characterize situations in which
it performs competitively with the SDP-based preconditioning. The second one is
based on SPA itself and can be interpreted as an optimal solution of a
relaxation of the SDP. It is extremely fast while competing with the SDP-based
preconditioning on several synthetic data sets.
