# American Institute of Mathematical Sciences

August  2015, 9(3): 917-933. doi: 10.3934/ipi.2015.9.917

## Hyperspectral unmixing by the alternating direction method of multipliers

 1 EO-Stat Inc. of North Carolina, 10010 Vail Dr., Chapel Hill, NC, 27517, United States 2 Department of Mathematics, University of California, Los Angeles, CA, 90095, United States

Received  June 2014 Revised  September 2014 Published  July 2015

We have developed a method for hyperspectral image data unmixing that requires neither pure pixels nor any prior knowledge about the data. Based on the well-established Alternating Direction Method of Multipliers, the problem is formulated as a biconvex constrained optimization with the constraints enforced by Bregman splitting. The resulting algorithm estimates the spectral and spatial structure in the image through a numerically stable iterative approach that removes the need for separate endmember and spatial abundance estimation steps. The method is illustrated on data collected by the SpecTIR imaging sensor.
Citation: Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
##### References:
 [1] S. Boyd, N. Parkh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1-122. doi: 10.1561/2200000016. [2] C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis, John Wiley & Sons, Hoboken, NJ, 2013. doi: 10.1002/9781118269787. [3] M. D. Craig, Minimum-volume transforms for remotely sensed data, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542-552. doi: 10.1109/36.297973. [4] T. Goldstein and S. Osher, The split Bregman method for l-1 regularized problems, SIAM J. on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891. [5] G. H. Golub, S. Nash and C. van Loan, A Hessenberg-Schur method for the problem $AX + XB = C$, IEEE Trans. Automatic Control, 24 (1979), 909-913. doi: 10.1109/TAC.1979.1102170. [6] J. A. Herweg, J. P. Kerekes, O. Weatherbee, D. Messinger, J. van Aardt, E. J. Ientilucci, Z. Ninkov, J. Fauling, N. Raqueno and J. Meda, SpecTIR Hyperspectral Airborne Rochester Experiment (SHARE) Data Collection Campaign, Proc. SPIE 8390, 2012. [7] M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), 303-320. doi: 10.1007/BF00927673. [8] R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems, UCLA CAM Report 12-39, 2012. [9] L. Miao and H. Qi, Endmember extraction from highly mixed data using minimum volume constrained nonnegative matrix factorization, IEEE Trans. Geosci. Remote Sens., 45 (2007), 765-777. doi: 10.1109/TGRS.2006.888466. [10] J. M. P. Nascimento and J. M. Bioucas Dias, Vertex component analysis: A fast algorithm to unmix hyperspectral data, IEEE Trans. Geosci. Remote Sens., 43 (2005), 898-910. doi: 10.1109/TGRS.2005.844293. [11] J. Nocedal and S. J. Wright, Numerical Optimization, Section 17.4, Springer, 1999. doi: 10.1007/b98874. [12] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, 283-298. [13] R. T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming, Journal of Optimization Theory and Applications, 12 (1973), 555-562. doi: 10.1007/BF00934777. [14] R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing, 2nd Ed., Academic Press, NY, 1997. [15] M. E. Winter, N-FINDR: An algorithm for fast autonomous spectral end-member determination in hyperspectral data, in Imaging Spectrometry V, 3753 (1999), 266-275. doi: 10.1117/12.366289. [16] The earlier algorithm was developed under Purchase Order 1010 P PA379 to EO-Stat, Inc. from UCLA under NSF, grant DMS-1118971., (). [17] Wide Area Arial Reconnaissance (WAAR) Project sponsored by the Edgewood Chemical Biological Center with data made available through the Advanced Threat Detection Program run by DTRA and NSF., Data collected by the Applied Physics Laboratory with a Telops Hyper-Cam sensor in 2009., Information supplied by Alison Carr of APL., ().

show all references

##### References:
 [1] S. Boyd, N. Parkh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1-122. doi: 10.1561/2200000016. [2] C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis, John Wiley & Sons, Hoboken, NJ, 2013. doi: 10.1002/9781118269787. [3] M. D. Craig, Minimum-volume transforms for remotely sensed data, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542-552. doi: 10.1109/36.297973. [4] T. Goldstein and S. Osher, The split Bregman method for l-1 regularized problems, SIAM J. on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891. [5] G. H. Golub, S. Nash and C. van Loan, A Hessenberg-Schur method for the problem $AX + XB = C$, IEEE Trans. Automatic Control, 24 (1979), 909-913. doi: 10.1109/TAC.1979.1102170. [6] J. A. Herweg, J. P. Kerekes, O. Weatherbee, D. Messinger, J. van Aardt, E. J. Ientilucci, Z. Ninkov, J. Fauling, N. Raqueno and J. Meda, SpecTIR Hyperspectral Airborne Rochester Experiment (SHARE) Data Collection Campaign, Proc. SPIE 8390, 2012. [7] M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), 303-320. doi: 10.1007/BF00927673. [8] R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems, UCLA CAM Report 12-39, 2012. [9] L. Miao and H. Qi, Endmember extraction from highly mixed data using minimum volume constrained nonnegative matrix factorization, IEEE Trans. Geosci. Remote Sens., 45 (2007), 765-777. doi: 10.1109/TGRS.2006.888466. [10] J. M. P. Nascimento and J. M. Bioucas Dias, Vertex component analysis: A fast algorithm to unmix hyperspectral data, IEEE Trans. Geosci. Remote Sens., 43 (2005), 898-910. doi: 10.1109/TGRS.2005.844293. [11] J. Nocedal and S. J. Wright, Numerical Optimization, Section 17.4, Springer, 1999. doi: 10.1007/b98874. [12] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, 283-298. [13] R. T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming, Journal of Optimization Theory and Applications, 12 (1973), 555-562. doi: 10.1007/BF00934777. [14] R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing, 2nd Ed., Academic Press, NY, 1997. [15] M. E. Winter, N-FINDR: An algorithm for fast autonomous spectral end-member determination in hyperspectral data, in Imaging Spectrometry V, 3753 (1999), 266-275. doi: 10.1117/12.366289. [16] The earlier algorithm was developed under Purchase Order 1010 P PA379 to EO-Stat, Inc. from UCLA under NSF, grant DMS-1118971., (). [17] Wide Area Arial Reconnaissance (WAAR) Project sponsored by the Edgewood Chemical Biological Center with data made available through the Advanced Threat Detection Program run by DTRA and NSF., Data collected by the Applied Physics Laboratory with a Telops Hyper-Cam sensor in 2009., Information supplied by Alison Carr of APL., ().
 [1] Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems and Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19 [2] Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems and Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048 [3] Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems and Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257 [4] Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems and Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199 [5] Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046 [6] Stefan Kindermann, Andreas Neubauer. On the convergence of the quasioptimality criterion for (iterated) Tikhonov regularization. Inverse Problems and Imaging, 2008, 2 (2) : 291-299. doi: 10.3934/ipi.2008.2.291 [7] Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations and Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034 [8] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [9] Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761 [10] Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems and Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295 [11] Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial and Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191 [12] Philipp Hungerländer, Barbara Kaltenbacher, Franz Rendl. Regularization of inverse problems via box constrained minimization. Inverse Problems and Imaging, 2020, 14 (3) : 437-461. doi: 10.3934/ipi.2020021 [13] Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems and Imaging, 2021, 15 (3) : 415-443. doi: 10.3934/ipi.2020074 [14] Xihong Yan. An augmented Lagrangian-based parallel splitting method for a one-leader-two-follower game. Journal of Industrial and Management Optimization, 2016, 12 (3) : 879-890. doi: 10.3934/jimo.2016.12.879 [15] Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $H^1$. Discrete and Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019 [16] Xinsheng Wang, Lin Wang, Yujun Zhu. Formula of entropy along unstable foliations for $C^1$ diffeomorphisms with dominated splitting. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2125-2140. doi: 10.3934/dcds.2018087 [17] Huiyuan Guo, Quan Yu, Xinzhen Zhang, Lulu Cheng. Low rank matrix minimization with a truncated difference of nuclear norm and Frobenius norm regularization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022045 [18] Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems and Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907 [19] Yoshikazu Giga, Jürgen Saal. $L^1$ maximal regularity for the laplacian and applications. Conference Publications, 2011, 2011 (Special) : 495-504. doi: 10.3934/proc.2011.2011.495 [20] Keith Promislow, Hang Zhang. Critical points of functionalized Lagrangians. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1231-1246. doi: 10.3934/dcds.2013.33.1231

2020 Impact Factor: 1.639