# 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 & 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. doi: 10.1561/2200000016. Google Scholar [2] C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis,, John Wiley & Sons, (2013). doi: 10.1002/9781118269787. Google Scholar [3] M. D. Craig, Minimum-volume transforms for remotely sensed data,, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542. doi: 10.1109/36.297973. Google Scholar [4] T. Goldstein and S. Osher, The split Bregman method for l-1 regularized problems,, SIAM J. on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. Google Scholar [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. doi: 10.1109/TAC.1979.1102170. Google Scholar [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, (8390). Google Scholar [7] M. R. Hestenes, Multiplier and gradient methods,, Journal of Optimization Theory and Applications, 4 (1969), 303. doi: 10.1007/BF00927673. Google Scholar [8] R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems,, UCLA CAM Report 12-39, (2012), 12. Google Scholar [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. doi: 10.1109/TGRS.2006.888466. Google Scholar [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. doi: 10.1109/TGRS.2005.844293. Google Scholar [11] J. Nocedal and S. J. Wright, Numerical Optimization,, Section 17.4, (1999). doi: 10.1007/b98874. Google Scholar [12] M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in Optimization (Sympos., (1968), 283. Google Scholar [13] R. T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming,, Journal of Optimization Theory and Applications, 12 (1973), 555. doi: 10.1007/BF00934777. Google Scholar [14] R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing,, 2nd Ed., (1997). Google Scholar [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. doi: 10.1117/12.366289. Google Scholar [16] The earlier algorithm was developed under Purchase Order 1010 P PA379 to EO-Stat, Inc. from UCLA under NSF, grant DMS-1118971., (). Google Scholar [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., (). Google Scholar

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. doi: 10.1561/2200000016. Google Scholar [2] C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis,, John Wiley & Sons, (2013). doi: 10.1002/9781118269787. Google Scholar [3] M. D. Craig, Minimum-volume transforms for remotely sensed data,, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542. doi: 10.1109/36.297973. Google Scholar [4] T. Goldstein and S. Osher, The split Bregman method for l-1 regularized problems,, SIAM J. on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. Google Scholar [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. doi: 10.1109/TAC.1979.1102170. Google Scholar [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, (8390). Google Scholar [7] M. R. Hestenes, Multiplier and gradient methods,, Journal of Optimization Theory and Applications, 4 (1969), 303. doi: 10.1007/BF00927673. Google Scholar [8] R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems,, UCLA CAM Report 12-39, (2012), 12. Google Scholar [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. doi: 10.1109/TGRS.2006.888466. Google Scholar [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. doi: 10.1109/TGRS.2005.844293. Google Scholar [11] J. Nocedal and S. J. Wright, Numerical Optimization,, Section 17.4, (1999). doi: 10.1007/b98874. Google Scholar [12] M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in Optimization (Sympos., (1968), 283. Google Scholar [13] R. T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming,, Journal of Optimization Theory and Applications, 12 (1973), 555. doi: 10.1007/BF00934777. Google Scholar [14] R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing,, 2nd Ed., (1997). Google Scholar [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. doi: 10.1117/12.366289. Google Scholar [16] The earlier algorithm was developed under Purchase Order 1010 P PA379 to EO-Stat, Inc. from UCLA under NSF, grant DMS-1118971., (). Google Scholar [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., (). Google Scholar
 [1] Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems & 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 & 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 & 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 & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199 [5] Stefan Kindermann, Andreas Neubauer. On the convergence of the quasioptimality criterion for (iterated) Tikhonov regularization. Inverse Problems & Imaging, 2008, 2 (2) : 291-299. doi: 10.3934/ipi.2008.2.291 [6] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [7] Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761 [8] Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems & Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295 [9] Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial & Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191 [10] Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034 [11] Xihong Yan. An augmented Lagrangian-based parallel splitting method for a one-leader-two-follower game. Journal of Industrial & Management Optimization, 2016, 12 (3) : 879-890. doi: 10.3934/jimo.2016.12.879 [12] Xinsheng Wang, Lin Wang, Yujun Zhu. Formula of entropy along unstable foliations for $C^1$ diffeomorphisms with dominated splitting. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2125-2140. doi: 10.3934/dcds.2018087 [13] Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907 [14] 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 [15] Jussi Korpela, Matti Lassas, Lauri Oksanen. Discrete regularization and convergence of the inverse problem for 1+1 dimensional wave equation. Inverse Problems & Imaging, 2019, 13 (3) : 575-596. doi: 10.3934/ipi.2019027 [16] Zhong Tan, Huaqiao Wang, Yucong Wang. Time-splitting methods to solve the Hall-MHD systems with Lévy noises. Kinetic & Related Models, 2019, 12 (1) : 243-267. doi: 10.3934/krm.2019011 [17] Keith Promislow, Hang Zhang. Critical points of functionalized Lagrangians. Discrete & Continuous Dynamical Systems - A, 2013, 33 (4) : 1231-1246. doi: 10.3934/dcds.2013.33.1231 [18] Markus Grasmair. Well-posedness and convergence rates for sparse regularization with sublinear $l^q$ penalty term. Inverse Problems & Imaging, 2009, 3 (3) : 383-387. doi: 10.3934/ipi.2009.3.383 [19] Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems & Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447 [20] C.M. Elliott, S. A. Smitheman. Analysis of the TV regularization and $H^{-1}$ fidelity model for decomposing animage into cartoon plus texture. Communications on Pure & Applied Analysis, 2007, 6 (4) : 917-936. doi: 10.3934/cpaa.2007.6.917

2018 Impact Factor: 1.469