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.

[2]

C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis,, John Wiley & Sons, (2013). doi: 10.1002/9781118269787.

[3]

M. D. Craig, Minimum-volume transforms for remotely sensed data,, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542. 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. 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. 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, (8390).

[7]

M. R. Hestenes, Multiplier and gradient methods,, Journal of Optimization Theory and Applications, 4 (1969), 303. doi: 10.1007/BF00927673.

[8]

R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems,, UCLA CAM Report 12-39, (2012), 12.

[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.

[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.

[11]

J. Nocedal and S. J. Wright, Numerical Optimization,, Section 17.4, (1999). doi: 10.1007/b98874.

[12]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in Optimization (Sympos., (1968), 283.

[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.

[14]

R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing,, 2nd Ed., (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. 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. doi: 10.1561/2200000016.

[2]

C.-I. Cheng, Hyperspectral Data Processing: Algorithm Design and Analysis,, John Wiley & Sons, (2013). doi: 10.1002/9781118269787.

[3]

M. D. Craig, Minimum-volume transforms for remotely sensed data,, IEEE Trans. Geosci. Remote Sens., 32 (1994), 542. 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. 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. 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, (8390).

[7]

M. R. Hestenes, Multiplier and gradient methods,, Journal of Optimization Theory and Applications, 4 (1969), 303. doi: 10.1007/BF00927673.

[8]

R. Lai and S. Osher, A Splitting Method for Orthogonally Constrained Problems,, UCLA CAM Report 12-39, (2012), 12.

[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.

[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.

[11]

J. Nocedal and S. J. Wright, Numerical Optimization,, Section 17.4, (1999). doi: 10.1007/b98874.

[12]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in Optimization (Sympos., (1968), 283.

[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.

[14]

R. A. Schowengerdt, Remote Sensing: Models and Methods for Image Processing,, 2nd Ed., (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. 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 & 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]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Seung-Yeal Ha, Eunhee Jeong, Robert M. Strain. Uniform $L^1$-stability of the relativistic Boltzmann equation near vacuum. Communications on Pure & Applied Analysis, 2013, 12 (2) : 1141-1161. doi: 10.3934/cpaa.2013.12.1141

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]