Consider a structured matrix factorization model where one factor is restricted to have its columns lying in the unit simplex. This simplex-structured matrix factorization (SSMF) model and the associated factorization techniques have spurred much interest in research topics over different areas, such as hyperspectral unmixing in remote sensing, topic discovery in machine learning, to name a few. In this paper we develop a new theoretical SSMF framework whose idea is to study a maximum volume ellipsoid inscribed in the convex hull of the data points. This maximum volume inscribed ellipsoid (MVIE) idea has not been attempted in prior literature, and we show a sufficient condition under which the MVIE framework guarantees exact recovery of the factors. The sufficient recovery condition we show for MVIE is much more relaxed than that of separable non-negative matrix factorization (or pure-pixel search); coincidentally it is also identical to that of minimum volume enclosing simplex, which is known to be a powerful SSMF framework for non-separable problem instances. We also show that MVIE can be practically implemented by performing facet enumeration and then by solving a convex optimization problem. The potential of the MVIE framework is illustrated by numerical results.
While MVES is appealing in its recovery guarantees, the pursuit of SSMF frameworks is arguably not over. The MVES problem is non-convex and NP-hard in general @cite_21 . Our numerical experience is that the convergence of an MVES algorithm to a good result could depend on the starting point. Hence, it is interesting to study alternative frameworks that can also go beyond the pure-pixel or separability case and can bring new perspective to the no-pure-pixel case---and this is the motivation for our development of the MVIE framework in the next section.
@cite_21
2050041778 2095343758 2743180144 2170078675
Hyperspectral unmixing aims at identifying the hidden spectral signatures (or endmembers) and their corresponding proportions (or abundances) from an observed hyperspectral scene. Many existing hyperspectral unmixing algorithms were developed under a commonly used assumption that pure pixels exist. However, the pure-pixel assumption may be seriously violated for highly mixed data. Based on intuitive grounds, Craig reported an unmixing criterion without requiring the pure-pixel assumption, which estimates the endmembers by vertices of a minimum-volume simplex enclosing all the observed pixels. In this paper, we incorporate convex analysis and Craig's criterion to develop a minimum-volume enclosing simplex (MVES) formulation for hyperspectral unmixing. A cyclic minimization algorithm for approximating the MVES problem is developed using linear programs (LPs), which can be practically implemented by readily available LP solvers. We also provide a non-heuristic guarantee of our MVES problem formulation, where the existence of pure pixels is proved to be a sufficient condition for MVES to perfectly identify the true endmembers. Some Monte Carlo simulations and real data experiments are presented to demonstrate the efficacy of the proposed MVES algorithm over several existing hyperspectral unmixing methods. Linear spectral unmixing aims at estimating the number of pure spectral substances, also called endmembers ,t heir spectral signatures, and their abundance fractions in remotely sensed hyperspectral images. This paper describes a method for unsupervised hyperspectral unmixing called minimum volume simplex analysis (MVSA) and introduces a new computationally efficient implementation. MVSA approaches hyperspectral un- mixing by fitting a minimum volume simplex to the hyperspec- tral data, constraining the abundance fractions to belong to the probability simplex. The resulting optimization problem, which is computationally complex, is solved in this paper by implementing a sequence of quadratically constrained subproblems using the interior point method, which is particularly effective from the computational viewpoint. The proposed implementation (available online: www.lx.it.pt 7ejun DemoMVSA.zip) is shown to exhibit state-of-the-art performance not only in terms of unmixing accu- racy, particularly in nonpure pixel scenarios, but also in terms of computational performance. Our experiments have been con- ducted using both synthetic and real data sets. An important assumption of MVSA is that pure pixels may not be present in the hyperspectral data, thus addressing a common situation in real scenarios which are often dominated by highly mixed pixels. In our experiments, we observe that MVSA yields competitive perfor- mance when compared with other available algorithms that work under the nonpure pixel regime. Our results also demonstrate that MVSA is well suited to problems involving a high number of endmembers (i.e., complex scenes) and also for problems involving a high number of pixels (i.e., large scenes). Most blind hyperspectral unmixing methods exploit convex geometry properties of hyperspectral data. The minimum volume simplex analysis (MVSA) is one of such methods, which, as many others, estimates the minimum volume (MV) simplex where the measured vectors live. MVSA was conceived to circumvent the matrix factorization step often implemented by MV-based algorithms and also to cope with outliers, which compromise the results produced by MV algorithms. Inspired by the recently proposed robust MV enclosing simplex (RMVES) algorithm, we herein introduce the robust MVSA (RMVSA), which is a version of MVSA robust to noise. As in RMVES, the robustness is achieved by employing chance constraints, which control the volume of the resulting simplex. RMVSA differs, however, substantially from RMVES in the way optimization is carried out. In this paper, we develop a linearization relaxation of the nonlinear chance constraints, which can greatly lighten the computational complex of chance constraint problems. The effectiveness of RMVSA is illustrated by comparing its performance with the state of the art. Effective unmixing of hyperspectral data cube under a noisy scenario has been a challenging research problem in remote sensing arena. A branch of existing hyperspectral unmixing algorithms is based on Craig's criterion, which states that the vertices of the minimum-volume simplex enclosing the hyperspectral data should yield high fidelity estimates of the endmember signatures associated with the data cloud. Recently, we have developed a minimum-volume enclosing simplex (MVES) algorithm based on Craig's criterion and validated that the MVES algorithm is very useful to unmix highly mixed hyperspectral data. However, the presence of noise in the observations expands the actual data cloud, and as a consequence, the endmember estimates obtained by applying Craig-criterion-based algorithms to the noisy data may no longer be in close proximity to the true endmember signatures. In this paper, we propose a robust MVES (RMVES) algorithm that accounts for the noise effects in the observations by employing chance constraints. These chance constraints in turn control the volume of the resulting simplex. Under the Gaussian noise assumption, the chance-constrained MVES problem can be formulated into a deterministic nonlinear program. The problem can then be conveniently handled by alternating optimization, in which each subproblem involved is handled by using sequential quadratic programming solvers. The proposed RMVES is compared with several existing benchmark algorithms, including its predecessor, the MVES algorithm. Monte Carlo simulations and real hyperspectral data experiments are presented to demonstrate the efficacy of the proposed RMVES algorithm.