Convex Cone Analysis (CCA)

Unsupervised endmember discovery & classification for multispectral/hyperspectral data

Intuition

  • Radiance/reflectance values are non‑negative ⇒ spectra live in the positive orthant.
  • Data form a convex cone spanned by a few underlying “pure” spectra (endmembers).
  • Goal: estimate the cone’s corners (extreme spectra). Then use them for unmixing or classification.

Think: any mixed pixel ≈ non‑negative combo of a small set of pure spectra.

Setup (Notation)

  • N pixels, B spectral bands, c components (endmembers/classes).
  • Build sample spectral correlation matrix R.
  • Compute top c eigenvectors EV₁…EV_c (basis of a low‑dimensional subspace).
  • Find non‑negative linear combinations inside this basis whose entries hit zero → cone corners.

Tip: Normalize spectra (e.g., unit norm) to remove brightness/illumination and keep shape.

Algorithm — Step by Step

  1. Preprocess: remove bad bands; offset‑correct if needed; normalize each pixel spectrum.
  2. Correlation & SVD: compute R; take eigenvectors with largest eigenvalues → EV₁…EV_c.
  3. Corner search (convex cone): solve small systems formed by setting c‑1 spectral dimensions to zero and checking non‑negativity to get candidate corners.
  4. Select corners (if many): keep a minimally collinear set (e.g., by correlation/condition number) closest to the data cloud.
  5. Use them:
    • Classification: matched filter or spectral angle with corner spectra.
    • Unmixing: non‑negative least squares (through origin) for fractional abundances.

Time & Space Complexity (define your “n”)

Let N=pixels, B=bands, c=components (small).

  • Build R: computing a B×B correlation from N pixels ≈ O(N·B²).
  • SVD / Eigen of B×B: O(B³).
  • Cone corner search (dominant when B is large): enumerate C(B, c‑1) tuples; each solve/check ≈ O((c‑1)³ + B·c) ⇒ total ≈ O(C(B,c‑1)·((c‑1)³ + B·c)).
  • Overall: for small fixed c, dominated by O(N·B² + B³ + B^{c‑1}). If you call input size n:
    • when n=N (pixels), cost is near‑linear in N (O(N·B²)) plus terms independent of N;
    • the exponential‑in‑c part is w.r.t. bands B, not pixels N.
  • Space: store data streaming or in chunks; main memory for R is O(B²); corners O(B·K) (K corners kept).

Rule of thumb: for modest B (≤50) and small c (2–5), SVD is cheap; the corner search can be the bottleneck.

Strengths, Weaknesses & Practical Tips

Strengths

  • Unsupervised: no library required; discovers endmembers from data.
  • Physically meaningful: exploits non‑negativity; corners map to extreme spectra.
  • No local minima: search/closed‑form corner construction (not iterative clustering).
  • Simple downstream: matched filters or NNLS for classification/unmixing.

Weaknesses

  • Corner search cost grows combinatorially with B and c.
  • Must handle negative values (noise/calibration) or cone breaks.
  • Requires a good guess of c (components).
  • If endmembers are highly collinear, corners proliferate & selection gets tricky.
  • Corner spectra may be farther than true endmembers ⇒ abundance scale bias.

Tips

Use this slide as your “discussion” page: what worked, what failed, and why.