Introduction to Prototype Analysis
In hyperspectral image processing, prototype analysis (Archetypal Analysis, AA) is an unsupervised method for endmember extraction and abundance estimation. Unlike conventional endmember extraction methods, prototype analysis does not assume that endmembers lie at the vertices of a simplex. Instead, it seeks the minimal convex hull of the original data points.
Given a hyperspectral data matrix \(\mathbf{X}=\left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n}, \ldots \mathbf{x}_{N}\right\} \in \mathbf{R}^{M \times N}\), where \(M\) is the number of spectral bands and \(N\) is the number of pixels, the goal of prototype analysis is to estimate \(D(D\ll N)\) prototypes \(\mathbf{Z}=\left\{\mathbf{z}_{1}, \mathbf{z}_{2}, \ldots, \mathbf{z}_{d}, \ldots \mathbf{z}_{D}\right\} \in \mathbf{R}^{M \times D}\) from \(\mathbf{X}\), so that each original observation \(\mathbf{x}_{n}\) can be written as a linear combination of the prototypes:
\[ \mathbf{x}_{n}=\mathbf{Z} s_{n} \]Correspondingly, each prototype \(\mathbf{z}_{d}\) can also be written as a linear combination of the original data:
\[ \mathbf{z}_{d}=\mathbf{X} \mathbf{c}_{d} \]where \(\mathbf{C} \in \mathbf{R}^{N \times D}\) is the coefficient matrix and \(\mathbf{S} \in \mathbf{R}^{D \times N}\) is the abundance matrix.
The objective of prototype analysis can be written as:
\[ \begin{array}{ll} \min _{\mathbf{C}, \mathbf{S}} & f(\mathbf{X} \mid \mathbf{X C S})=\|\mathbf{X}-\mathbf{X C S}\|_{F}^{2} \\ \text { s.t. } & \mathbf{C} \geq 0, \mathbf{S} \geq 0 \\ & \left\|\mathbf{c}_{d}\right\|_{1}=1,\left\|\mathbf{s}_{n}\right\|_{1}=1, \end{array} \]where \(\|\cdot\|_F\) denotes the Frobenius norm of a matrix. The constraints enforce nonnegativity of the coefficient matrix \(\mathbf{C}\) and the abundance matrix \(\mathbf{S}\), and require that the entries of each row (column) sum to 1.
To make prototype analysis more robust, a relaxation factor \(\boldsymbol{\alpha}\) can be introduced so that the prototypes need not lie strictly inside the convex hull of the original data points. The objective then becomes:
\[ \begin{array}{rl} \min _{\boldsymbol{\alpha}, \mathbf{C}, \mathbf{S}} & f(\mathbf{X} \mid \mathbf{X} \mathbf{C} \operatorname{diag}(\boldsymbol{\alpha}) \mathbf{S}) \\ \text { s.t. } & 1-\delta \leq \alpha_{d} \leq 1+\delta \\ & \mathbf{C} \geq 0, \mathbf{S} \geq 0 \\ & \left\|\mathbf{c}_{d}\right\|_{1}=1,\left\|\mathbf{s}_{n}\right\|_{1}=1 \end{array} \]where \(\delta\) is a parameter that controls how far the prototypes may deviate.
Hyperspectral Image Fusion Based on Prototype Analysis
Hyperspectral image fusion combines a hyperspectral image of low spatial resolution with a multispectral image of high spatial resolution, producing an image that has both high spectral resolution and high spatial resolution. Let the ideal hyperspectral image be \(\mathbf{Z}\), the low-spatial-resolution hyperspectral image be \(\mathbf{Y}\), and the high-spatial-resolution multispectral image be \(\mathbf{X}\). They can be written as:
\[ \begin{aligned} \mathbf{Z} &= \mathbf{Z}\mathbf{C}\mathbf{S} \\ \mathbf{Y} &= \mathbf{Z}\mathbf{P} = \mathbf{Z}\mathbf{C}\mathbf{S}\mathbf{P} \\ \mathbf{X} &= \mathbf{R}\mathbf{Z} = \mathbf{R}\mathbf{Z}\mathbf{C}\mathbf{S} \end{aligned} \]where \(\mathbf{P}\) is the spatial downsampling matrix and \(\mathbf{R}\) is the spectral response matrix. Under the least-squares criterion, the fusion objective can be written as:
\[ \begin{aligned} \min_{\mathbf{Z},\mathbf{C},\mathbf{S}}&\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Z}\mathbf{C}\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Z}\mathbf{C}\mathbf{S} \right\|_F^2 \end{aligned} \]After the relaxation factor \(\boldsymbol{\alpha}\) is introduced, the objective becomes:
\[ \begin{aligned} \min_{\mathbf{Z},\mathbf{C},\alpha, \mathbf{S}}&\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Z}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Z}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S} \right\|_F^2\\ \text { s.t. } & 1-\delta \leq \alpha_{d} \leq 1+\delta \\ \end{aligned} \]Because \(\mathbf{Z}\) is unknown, this model cannot be solved directly. A common approach is to first estimate an overcomplete endmember matrix \(\mathbf{Q}\) from \(\mathbf{Y}\) with an endmember extraction algorithm such as PPI, FPPI, or VCA, and then replace \(\mathbf{Z}\) by \(\mathbf{Q}\). The objective simplifies to:
\[ \begin{aligned} \min_{\mathbf{C},\alpha, \mathbf{S}}&\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S} \right\|_F^2\\ \text { s.t. } & 1-\delta \leq \alpha_{d} \leq 1+\delta \\ \end{aligned} \]To obtain a sparser solution, an \(\ell_1\)-norm regularization term can be introduced:
\[ \begin{aligned} \min_{\mathbf{C},\alpha, \mathbf{S}}&~\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S} \right\|_F^2+\left\|\mathbf{S} \right\|_1\\ \text { s.t. } &~1-\delta \leq \alpha_{d} \leq 1+\delta \\ &\mathbf{C}\succeq \mathbf{0}\\ & \mathbf{S} \succeq \mathbf{0}\\ \end{aligned} \]This objective can be solved by alternating optimization. The update steps are as follows:
\[ \begin{aligned} \mathbf{C}^{k + 1}\in &\mathop{argmin}\limits_{\mathbf{C}\succeq \mathbf{0}}\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Q}\mathbf{C}\operatorname{diag}(\alpha)\mathbf{S} \right\|_F^2\\ \alpha^{k + 1}\in &\mathop{argmin}\limits_{1-\delta \leq \alpha_{d} \leq 1+\delta}\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Q}\mathbf{C}^{k + 1}\operatorname{diag}(\alpha)\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Q}\mathbf{C}^{k + 1}\operatorname{diag}(\alpha)\mathbf{S} \right\|_F^2\\ \mathbf{S}^{k + 1}\in~ &\mathop{argmin}\limits_{\mathbf{S}\succeq \mathbf{0}}\frac{1}{2} \left\|\mathbf{Y} - \mathbf{Q}\mathbf{C}^{k + 1}\operatorname{diag}(\alpha^{k + 1})\mathbf{S}\mathbf{P}\right\|_F^2 + \frac{1}{2} \left\|\mathbf{X} -\mathbf{R}\mathbf{Q}\mathbf{C}^{k + 1}\operatorname{diag}(\alpha^{k + 1})\mathbf{S} \right\|_F^2+\left\|\mathbf{S} \right\|_1\\ \end{aligned} \]Here, \(\mathbf{C}\) and \(\boldsymbol{\alpha}\) are updated by the projected gradient method, and \(\mathbf{S}\) is updated by the ADMM algorithm.
Hyperspectral Image Unmixing Based on Prototype Analysis
In hyperspectral image unmixing, prototype analysis can also be used to estimate the endmember matrix \(\mathbf{A}\) and the abundance matrix \(\mathbf{S}\), so that:
\[ \begin{aligned} &\min \frac{1}{2}\|\mathbf{R}-\mathbf{R} \mathbf{C} \mathbf{S}\|_{F}^{2}\\ &\text { s.t. } \mathbf{C} \geq \mathbf{0}, \mathbf{1}_{n}^{T} \mathbf{C}=\mathbf{1}_{p}^{T}, \mathbf{S} \geq \mathbf{0}, \mathbf{1}_{p}^{T} \mathbf{S}=\mathbf{1}_{n}^{T} \end{aligned} \]where \(\mathbf{R}\) is the hyperspectral data matrix, \(n\) is the number of pixels, and \(p\) is the number of endmembers.
To account for spectral variability, an overcomplete set of data points \(\mathbf{Y}\) is first extracted from \(\mathbf{R}\) by the PPI algorithm. Constrained prototype analysis is then used to estimate the endmembers and the abundances:
\[ \begin{aligned} \arg \min &\frac{1}{2}|| \mathbf{Y} \mathbf{C} \operatorname{diag}(\boldsymbol{\alpha}) \mathbf{S}-\mathbf{R}\left\|_{F}^{2}+\lambda|| \mathbf{S}\right\|_{1}\\ &\text { s.t. } \mathbf{C} \geq \mathbf{0}, 1-\delta \leq \alpha_{i} \leq 1+\delta\\ &\mathbf{S} \geq \mathbf{0},\left\|c_{i}\right\|_{1}=1,\left\|s_{j}\right\|_{1} \leq 1 \end{aligned} \]where \(\lambda\) is a regularization parameter that controls the sparsity of the abundance matrix. This optimization problem can be solved by alternating optimization. The update steps are as follows:
\[ \begin{aligned} \boldsymbol{C}^{k+1} &=\underset{\boldsymbol{C} \geq 0,\left\|c_{i}\right\|_{1}=1}{\operatorname{argmin}} F\left(\boldsymbol{C}^{k}, \boldsymbol{\alpha}, \boldsymbol{S}\right) \\ \boldsymbol{\alpha}^{k+1} &=\underset{1-\delta \leq \alpha_{i} \leq 1+\delta}{\operatorname{argmin}} F\left(\boldsymbol{C}, \boldsymbol{\alpha}^{k}, \boldsymbol{S}\right) \\ \boldsymbol{S}^{k+1} &=\underset{\boldsymbol{S} \geq \mathbf{0},\left\|s_{j}\right\|_{1} \leq 1}{\operatorname{argmin}} F\left(\boldsymbol{C}, \boldsymbol{S}^{k}\right) \end{aligned} \]where \(F\) is the objective function:
\[ F=\frac{1}{2}\left\|\mathbf{Y} \widehat{\mathbf{C}} \mathbf{S}-\mathbf{R}\right\|_{F}^{2}+\lambda\|\mathbf{S}\|_{1} \]\(\widehat{\mathbf{C}}\) denotes \(\tilde{\mathbf{C}} \operatorname{diag}(\boldsymbol{\alpha})\).
\(\mathbf{C}\) and \(\boldsymbol{\alpha}\) are updated by the projected gradient method:
\[ \begin{aligned} \mathbf{C}^{k+1}&=\max \left(0, \mathbf{C}^{k}-\mu_{C}^{k} \nabla_{C} F\left(\mathbf{C}^{k}, \mathbf{S}^{k}\right)\right)\\ \boldsymbol{\alpha}^{k+1}&=P_{\alpha}\left[\boldsymbol{\alpha}^{k}-\mu_{\alpha}^{k} \nabla_{\alpha} F\left(\boldsymbol{\alpha}^{k}\right)\right] \end{aligned} \]where \(\mu_C^k\) and \(\mu_\alpha^k\) are step sizes obtained by line search. \(P_\alpha\) is a projection operator that constrains \(\boldsymbol{\alpha}\) to the interval \([1-\delta, 1+\delta]\).
The update of \(\mathbf{S}\) is solved by the ADMM algorithm:
\[ \begin{aligned} \mathbf{z}^{k+1}&=\operatorname{argmin} \lambda\left\|\mathbf{z}^{k}\right\|_{1}+\frac{\mu}{2}\left\|\mathbf{S}^{k}-\mathbf{z}^{k}-\mathbf{d}^{k}\right\|_{F}^{2}\\ \mathbf{S}^{k+1}&=\underset{\mathbf{S} \geq \mathbf{0},\left\|s_{j}\right\|_{1} \leq 1}{\operatorname{argmin}} \frac{1}{2}\left\|\mathbf{A} \mathbf{S}-\mathbf{R}\right\|_{F}^{2}+\frac{\mu}{2}\left\|\mathbf{S}-\mathbf{z}^{k+1} \mathbf{d}\right\|_{F}^{2}\\ \mathbf{d}^{k+1}&=\mathbf{d}^{k}-\left(\mathbf{S}^{k+1}-\mathbf{z}^{k+1}\right) \end{aligned} \]where \(\mathbf{A}=\mathbf{Y} \widehat{\mathbf{C}}\), and \(\mathbf{z}\) and \(\mathbf{d}\) are auxiliary variables.
The update of \(\mathbf{z}\) can be carried out efficiently with the soft-thresholding operator:
\[ \mathbf{z}^{k+1}=\operatorname{soft}\left(\mathbf{z}^{k+1}-\mathbf{d}, \frac{\lambda}{\mu}\right) \]The update of \(\mathbf{S}\) follows the fast gradient mapping (FGM) algorithm. The steps are as follows:
| |
where \(\Delta^p\) is the unit simplex, \(P_\Delta\) is a projection operator that constrains \(\mathbf{S}\) to lie in \(\Delta^p\), and \(L_f\) is the Lipschitz constant of the objective \(f\).
The overall algorithm is as follows:
| |
The discussion above covers the main mathematical principles and the solution procedure of hyperspectral image processing based on prototype analysis. The method is highly robust: it can handle noise and outliers effectively, and it performs well on tasks such as hyperspectral image fusion and unmixing.
