Source-linked AI summary
Generalized Alternating Projection Based Total Variation Minimization for Compressive Sensing
Xin Yuan
TL;DR
Compressive sensing reconstruction can depend on choosing a suitable transformation, while TV minimization offers an alternative formulation. The paper develops GAP-based TV minimization and reports strong results across images, videos, and hyperspectral images, while deriving ADMM formulations and relating the two methods.
Problem
Transformation-domain GAP requires selecting transformations, groups, and weights, motivating a GAP approach for TV minimization in compressive sensing.
Method
The paper develops generalized alternating projection based TV minimization and derives ADMM formulations for video and hyperspectral compressive sensing.
Results
Excellent results are demonstrated for compressive sensing of 2D images, videos, and hyperspectral images, including tests across high and extremely low CSr regimes for images.
Takeaways & Limitations
GAP-TV provides an almost parameter-free alternative for video compressive sensing, while GAP and ADMM differ in the x-update and ADMM performance depends critically on η.
Takeaways & Limitations
Transformation-domain alternatives require finding a suitable transformation and selecting groups and weights, while the GAP projection assumes ΦΦ⊤ is invertible.
Abstract
from arXiv · showhide
We consider the total variation (TV) minimization problem used for compressive sensing and solve it using the generalized alternating projection (GAP) algorithm. Extensive results demonstrate the high performance of proposed algorithm on compressive sensing, including two dimensional images, hyperspectral images and videos. We further derive the Alternating Direction Method of Multipliers (ADMM) framework with TV minimization for video and hyperspectral image compressive sensing under the CACTI and CASSI framework, respectively. Connections between GAP and ADMM are also provided.
1. INTRODUCTION
GAP has performed well across diverse compressive-sensing problems, but prior demonstrations used transformation-domain formulations. The paper therefore asks whether GAP can solve TV minimization directly.
- GAP has demonstrated strong performance on 2D images, hyperspectral images, videos, depth images, and polarization images.
- Prior GAP demonstrations, including real-system applications, solved compressive sensing in the wavelet or DCT transformation domain.
- Transformation-domain methods require selecting a suitable transformation T, which can add computation and affect results through group and weight selection.
- TV-based algorithms also achieve high performance on various compressive-sensing problems.
- The paper develops a GAP algorithm to solve the TV minimization problem under the compressive-sensing constraint.
2. MATHEMATIC FORMULATION
The formulation represents TV minimization as a constrained optimization problem and recasts it under GAP as alternating projections with an auxiliary variable.
- For images and videos, the TV norm is defined as ∥TV(x)∥ = ∥Dx∥1, with D applied across different dimensions.
- Under GAP, the TV minimization problem is rewritten using a constraint involving the radius C of the TV-based ℓ1-ball.
- The reformulated problem is solved as a series of alternating projection problems.
- The iterative formulation includes a regularizer λ and iteration index t.
3. GAP-TV ALGORITHM
GAP-TV alternates Euclidean projection with TV denoising, while ADMM uses an additional regularizer in its x-update. Special sensing structures make the updates efficient, and η strongly affects ADMM performance.
- GAP-TV algorithm: Given θ, GAP updates x by Euclidean projection onto the linear measurement manifold.
- GAP-TV algorithm: The projection assumes ΦΦ⊤ is invertible; in many compressive-sensing applications it is diagonal, simplifying inversion.
- GAP-TV algorithm: Given θ, the x-update also involves a TV denoising problem solved with an iterative clipping algorithm.
- Relation to ADMM: ADMM introduces an additional regularizer η and solves cyclic subproblems, including a quadratic optimization for x.
- Relation to ADMM: Because Φ is fat, ADMM uses a matrix inversion formula to simplify the large-matrix x-update.
- Relation to ADMM: For 2D image sensing with a permuted Hadamard matrix, ΦΦ⊤ = I, making the update match GAP when η = 0.
- Special sensing structures: For video and hyperspectral sensing, shifting binary masks yield diagonal ΦΦ⊤ structures and efficient x-updates.
- Relation to ADMM: GAP uses Euclidean projection without a parameter to tune x, whereas ADMM’s η critically affects experimental performance.
4. SIMULATION
The simulations evaluate GAP-TV for 2D images, CACTI video sensing, and CASSI hyperspectral sensing. Results use diverse sensing ratios and compare reconstruction PSNR across algorithms.
- 4.1. CS of 2D image: 2D image experiments use a permuted Hadamard sensing matrix and test GAP-TV across high and extremely low CSr regimes.Images are resized to 256 × 256; the extremely low CSr range targets applications less concerned with image quality.
- 4.2. Video CS: GAP-TV is applied to video compressive sensing under the coded aperture compressive temporal imaging (CACTI) framework.The video sensing process uses shifted binary masks to encode successive frames.
- 4.2. Video CS: For CACTI video sensing, each measurement combines frames modulated by shifted binary masks through element-wise multiplication.The formulation represents the f-th frame and its corresponding mask for the m-th measurement.
- 4.2. Video CS: Video simulations compare GAP-TV with other reconstruction algorithms using per-frame PSNR, with T = 8.The traffic sequence is evaluated by plotting the PSNR of each reconstructed frame.
- 4.3. Hyperspectral Image CS: CASSI hyperspectral experiments modulate each bandwidth frame with a shifted physical mask and evaluate the “bird” data.Reconstruction PSNR is reported for each frame with different algorithms.
5. CONCLUSION
The paper develops GAP-TV for compressive sensing and demonstrates results on images, videos, and hyperspectral images. Reconstruction PSNR is compared across diverse images, algorithms, and sensing ratios.
- 5. CONCLUSION: The proposed generalized alternating projection based total variation minimization algorithm targets compressive sensing of images, videos, and hyperspectral images.The conclusion reports excellent results across these three data types.
- 5. CONCLUSION: Table 1 reports reconstruction PSNR (dB) for different images and algorithms at various CSr values.The table organizes reconstruction quality by image, algorithm, and compressive sensing ratio.