8.1 Introduction

In order to find endmembers, two general approaches have been used in the past. One approach extracts all required endmembers simultaneously, referred to as simultaneous endmember extraction algorithm (SM-EEA) that has already been studied in Chapter 7. The other approach extracts endmembers one at a time sequentially, referred to as sequential EEA (SQ-EEA) which will be discussed in this chapter. In general, extraction of endmembers must be performed by finding all endmembers at once. Hence, an optimal EEA should be an SM-EEA. Unfortunately, this also requires an SM-EEA to conduct an exhaustive search for an optimal set of endmembers. Computationally speaking, this may not be a good option because the process will be extremely slow, especially when the number of endmembers grows. On the other hand, an SQ-EEA can become an acceptable alternative even if it may not be as optimal as an SM-EEA. As will be demonstrated by experiments, in most cases, an SQ-EEA is comparable to an SM-EEA with regard to performance of endmember extraction. Most importantly, two benefits gained by an SQ-EEA can really remedy two major drawbacks suffered from an SM-EEA. One benefit is significant reduction in computing time resulting from SQ-EEA that only needs to find one endmember at a time sequentially without finding all endmembers simultaneously as required by SM-EEA. The second benefit is that SQ-EEA retains previously generated endmembers while continuing to add new endmembers, an advantage that cannot be gaineded from SM-EEA. In particular, if the total number of endmembers to be extracted changes, SM-EEA must resume its exhaustive search as a new process for finding all new endmembers, and endmembers previously generated by SM-EEA for a small number of endmembers cannot be used as part of new endmembers. By contrast, SQ-EEA can always use previously generated endmembers as the starting point and continue to produce new endmembers afterwards. Interestingly, as will be shown in this chapter, an SM-EEA can always find its SQ-EEA counterpart so that both algorithms can produce similar results.

As noted in Chapter 7, for an EEA to be optimal it ought to be an SM-EEA that must conduct an exhaustive search for all endmembers at once. For example, for the N-FINDR to produce p endmembers among N data sample vectors a total of searches must be conducted and the simplex volume specified by (7.5) must be recalculated for each of the searches. If the value of N becomes large, the computational complexity will increase exponentially and become formidable very quickly and going out of control. Therefore, two options can be adopted to alleviate this dilemma. One option narrows down a searching region to a feasible range. This practice is actually exercised in step 5 in SM N-FINDR, steps 4 and 5 in SPCA-EEA, and step 4 in FCLS-EEA discussed in Chapter 7, where their replacement rules are carried out in two loops (inner and outer loops) instead of being performed simultaneously. However, even in this case, the computation task can still be very high. Thus, a more pragmatic solution is to convert an SM-EEA into an SQ-EEA so that the computation can be reduced greatly by finding endmembers one at a time rather than all endmembers being generated at the same time. For example, we may implement an SM N-FINDR via its inner loop without running its outer loop, as discussed in Section 7.2.3.4. However, this is easier said than done. It is, in general, not a trivial matter since we need to make ensure that such an SM-EEA-to-SQ-EEA conversion via the use of only the inner loop will not be traded for poor performance. This chapter deals with this issue and develops such SQ-EEAs for this reason.

Like SM-EEA, the first issue that needs to be addressed for SQ-EEA is to determine how many endmembers, p, are required for SQ-EEA to generate before it is terminated. The virtual dimensionality (VD) developed in Chapter 5 that is used to determine the value of p for SM-EEAs in Chapter 7 is also applicable to SQ-EEAs. Once the p is determined, the second issue is to design an algorithm that can search endmembers one by one sequentially. Four types of SQ-EEAs are of particular interest and will be presented in this chapter.

The first type of SQ-EEAs is orthogonal projection (OP)-based EEAs. A representative is vertex component analysis (VCA) that has recently developed by Nascimento and Dias (2005). This implements a similar idea to that used in the MVT and CCA to find a maximal projection convex hull, but has two different aspects. One is that VCA is an SQ-EEA, not an SM-EEA, as MVT and CCA are. The other is that VCA performs OP to find endmembers instead of finding the maximal simplex volume, as performed by MVT and CCA. Because VCA uses OP in the same manner as PPI, developed in Chapter 7, which also uses OP to find endmembers, it can be considered an SQ-EEA counterpart of PPI. Their relationship will be further explored further in Chapter 11. In addition, as a result of its use of a sequential search via OP rather than solving maximal simplex volume optimization, VCA is considered to be among the fastest EEAs that are currently being used in the literature. However, its performance is generally not as good as what we expect due to the fact that finding maximal OP does not necessarily yield a convex hull with maximal-volume.

A second type of SQ-EEAs of interest is sequential versions of IN-FINDR, as proposed in Chapter 7. One is called successive IN-FINDR (SC IN-FINDR) presented in Section 7.2.3. Since IN-FINDR repeatedly searches for a set of new p vertices simultaneously by using two loops until it finds a p-vertex simplex with maximal volume, it can be viewed as simultaneous N-FINDR (SM-N-FINDR). So, if the number p is large, IN-FINDR becomes very slow. In this case, SC IN-FINDR can be used instead to reduce computing time. The other is called the simplex growing algorithm (SGA) developed by Chang et al. (2006), which finds a desired p-dimensional simplex with maximal volume by gradually growing simplexes with maximal volumes vertex by vertex. In other words, instead of directly finding a p-vertex simplex with maximal volume as N-FINDR and its variants do, it first finds a two-vertex simplex with largest volume from which it begins to grow new simplexes with largest volumes by increasing vertices from 2 to p. Since it generates desired endmembers one by one by a simplex growing process, SGA is indeed an SQ-EEA. Using such a simplex growing implementation, SGA only has to find one endmember at a time until it reaches a desired number of endmembers, p. This is completely different from IN-FINDR that replaces vertices of simplexes in the outer loop with a complete new set of vertices repeatedly obtained from its inner loop. Like VCA, SGA is also among the fastest EEAs due to its use of a sequential search process. However, since the OP used in VCA requires less amount of computing time than the calculation of a simplex volume used by SGA, VCA performs faster than SGA in computation. Nevertheless, it should be noted that a faster EEA is not necessarily a better EEA. As demonstrated by experiments, SGA actually performed better than VCA in terms of endmember extraction performance at the expense of higher computation.

The third type of SQ-EEAs is least-squares error (LSE)-based EEAs that include automatic target generation process EEA (ATGP-EEA) originated by Ren and Chang (2003) which implements successive orthogonal subspace projections (OSPs) to find endmembers, unsupervised nonnegativity least-squares EEA (UNCLS-EEA) derived by Chang and Heinz (2000) that uses the abundance nonnegativity constraint to find successive endmembers, unsupervised fully constrained least-squares EEA (UFCLS-EEA) developed by Heinze and Chang (2001) that is derived from FCLS-EEA in Chapter 7, iterative error analysis-EEA (IEA-EEA) proposed by Neville et al. (1999) that is essentially identical to UFCLS-EEA in the sense that both use a full abundance constrained spectral unmixing technique to find endmembers.

Finally, the fourth type of SQ-EEAs is projection pursuit (PP)-based EEAs that include high-order statistics (HOS)-based EEAs and independent component analysis (ICA)-based EEAs; both of them have no SM-EEA counterparts in Chapter 7 but can be derived from dimensionality reduction by transform as discussed in Chapter 6. SQ-EEAs of this type produce a sequence of successive components characterized by projection indices, such as skewness specified by the third-order statistics, kurtosis described by the fourth-order statistics, kth moment, statistical independence measured by mutual information so that each component can be used to extract a particular endmember. The idea behind PP-based EEAs is to assume that endmembers can be characterized by statistics of high orders due to their rarity, small sample pool, and occurrence with low probabilities. This rationale is based on several observations. First, since distinct endmembers represent different spectral classes, their statistical dependency must be least correlated. Second, because the nature of endmembers is of pure signatures the probability of occurrence of endmembers is generally low. Third, when endmembers do occur, the spatial extent of their presence is usually very limited and small. Of particular interest among HOS-based EEAs is the ICA (Hyvarinen et al., 2001), which is a blind source separation technique that unmixes a linear mixture of statistically independent signal sources. If the signal sources to be unmixed are interpreted as sources of pure signatures, its applicability to endmember extraction seems natural and justifiable (Wang and Chang, 2006b).