Hybrid Inexact BCD for Coupled Structured Matrix Factorization in Hyperspectral Super-Resolution

Ruiyuan Wu, Hoi-To Wai, Wing-Kin MaIEEE TSP 2020 · OpenReview

Abstract

This paper develops a first-order optimization method for coupled structured matrix factorization (CoSMF) problems that arise in the context of hyperspectral super-resolution (HSR) in remote sensing. To best leverage the problem structures for computational efficiency, we introduce a hybrid inexact block coordinate descent (HiBCD) scheme wherein one coordinate is updated via the fast proximal gradient (FPG) method, while another via the Frank-Wolfe (FW) method. The FPG-type methods are known to take less number of iterations to converge, by numerical experience, while the FW-type methods can offer lower per-iteration complexity in certain cases; and we wish to take the best of both. We show that the limit points of this HiBCD scheme are stationary. Our proof treats HiBCD as an optimization framework for a class of multi-block structured optimization problems, and our stationarity claim is applicable not only to CoSMF but also to many other problems. Previous optimization research showed the same stationarity result for inexact block coordinate descent with either FPG or FW updates only. Numerical results indicate that the proposed HiBCD scheme is computationally much more efficient than the state-of-the-art CoSMF schemes in HSR.

Introduction

In the world of remote sensing, researchers often face a frustrating trade-off: images can have incredible spectral detail (hyperspectral) but blurry spatial resolution, or sharp spatial shapes (multispectral) but limited color information. Hyperspectral Super-Resolution (HSR) is the process of fusing these two data types to create a single "super-image" that is both sharp and spectrally rich.

A recent paper by Ruiyuan Wu and colleagues introduces a clever optimization framework called HiBCD (Hybrid Inexact Block Coordinate Descent) that makes this fusion process significantly faster and more efficient by leveraging the specific mathematical structures of the problem.

The HSR Problem Model

To reconstruct a high-resolution hyperspectral image, researchers use a technique called Coupled Structured Matrix Factorization (CoSMF). Mathematically, the goal is to find two matrices: $A$ (the spectral signatures of materials) and $S$ (the spatial distribution or abundances of those materials).

The HSR problem setup involving linear spectral mixture modeling and observation models for hyperspectral and multispectral sensors.

As illustrated in Figure 1, the linear spectral mixture model represents the super-resolution (SR) image as a combination of spectral signatures and spatial maps. The observation model describes how this SR image is decimated—spatially for the hyperspectral (HS) sensor and spectrally for the multispectral (MS) sensor. The challenge lies in the fact that this is a large-scale, non-convex problem with millions of variables.

Methods: The HiBCD Framework

The core innovation is the Hybrid Inexact Block Coordinate Descent (HiBCD) scheme. Instead of treating every part of the puzzle the same way, the authors use a hybrid approach that selects the best optimization "engine" for each matrix:

  1. FPG for Spectral Signatures ($A$): The Fast Proximal Gradient (FPG) method is used for the spectral matrix. FPG is known for needing very few iterations to converge, which is ideal for the relatively simple constraints applied to $A$.
  2. FW for Spatial Abundances ($S$): The Frank-Wolfe (FW) method is used for the spatial matrix. FW is computationally "cheap" per iteration. This is crucial for $S$, especially when applying complex constraints like the Nuclear Norm to ensure the image has a low-rank structure. While other methods would require an expensive Singular Value Decomposition (SVD) at every step, FW uses a much simpler linear optimization oracle.
  3. Custom Step-Sizes: The authors derived specific, "tight" step-size rules tailored to the quadratic nature of the HSR problem, ensuring the algorithm takes the largest possible step toward the solution without overshooting.

Key Results and Insights

The authors evaluated HiBCD using the Chikusei dataset (an urban area in Japan) and synthetic data from the USGS spectral library. The results highlight a "best of both worlds" outcome:

  • Massive Speedup: In the Chikusei experiment, the HiBCD (FPG-FW) approach was roughly 10x faster than FUMI and 2x faster than SupResPALM, two state-of-the-art competitors.
  • Efficiency in Complexity: For Nuclear Norm Constrained problems, the hybrid scheme was nearly 5x faster than using FPG for both blocks, primarily because it avoided the heavy computational burden of full SVDs.
  • High Fidelity: Despite the speed, there was no trade-off in quality. HiBCD achieved lower (better) ERGAS scores and higher PSNR (Peak Signal-to-Noise Ratio) compared to most baseline methods.

Conclusion

The paper demonstrates that "inexactness" in optimization can be a virtue. By taking smart, computationally inexpensive steps in the right direction for each block, HiBCD achieves state-of-the-art accuracy with a massive boost in speed. Future work may extend this logic to 3D tensor factorizations to better capture the multi-dimensional nature of hyperspectral data.

Reference: Wu, R., Wai, H.-T., & Ma, W.-K. (2020). Hybrid Inexact BCD for Coupled Structured Matrix Factorization in Hyperspectral Super-Resolution. arXiv:1909.09183v3.

Summary updated

Abstract

This paper develops a first-order optimization method for coupled structured matrix factorization (CoSMF) problems that arise in the context of hyperspectral super-resolution (HSR) in remote sensing. To best leverage the problem structures for computational efficiency, we introduce a hybrid inexact block coordinate descent (HiBCD) scheme wherein one coordinate is updated via the fast proximal gradient (FPG) method, while another via the Frank-Wolfe (FW) method. The FPG-type methods are known to take less number of iterations to converge, by numerical experience, while the FW-type methods can offer lower per-iteration complexity in certain cases; and we wish to take the best of both. We show that the limit points of this HiBCD scheme are stationary. Our proof treats HiBCD as an optimization framework for a class of multi-block structured optimization problems, and our stationarity claim is applicable not only to CoSMF but also to many other problems. Previous optimization research showed the same stationarity result for inexact block coordinate descent with either FPG or FW updates only. Numerical results indicate that the proposed HiBCD scheme is computationally much more efficient than the state-of-the-art CoSMF schemes in HSR.
BibTeX
@article{wu2020hybrid,
  author = {Ruiyuan Wu and Hoi-To Wai and Wing-Kin Ma},
  title = {{Hybrid Inexact BCD for Coupled Structured Matrix Factorization in Hyperspectral Super-Resolution}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=ndr_lcrxxwe},
}
Figure