Abstract
Signal sparse matrix structure and the degree of relationship between signal sparse representations significantly affect the recovery reconstruction performance in compressed sensing. Traditional dictionary learning (DL) algorithms, such as K-SVD and Online Dictionary Learning (OLM), often suffer from high computational complexity and a lack of convergence guarantees. This paper proposes a fast dictionary learning algorithm based on proximal gradient (FDL_PG). By applying convex optimization principles and reducing iterative overhead, the algorithm ensures convergence while significantly decreasing computation time. Experiments on synthetic data demonstrate that FDL_PG achieves superior speed and dictionary quality compared to existing methods.
Introduction
In the field of Compressed Sensing (CS), signals are assumed to be sparse, meaning they can be represented by a few "atoms" from a dictionary. Finding an optimal dictionary for specific signal classes is the goal of Dictionary Learning (DL).
Existing methods like K-SVD and OLM face two major hurdles:
- Computational Complexity: Reliance on expensive operations like Singular Value Decomposition (SVD) leads to slow performance as data size increases.
- Convergence Issues: Many traditional algorithms are heuristic and lack strict global convergence guarantees.
The proposed Fast Dictionary Learning via Proximal Gradient (FDL_PG) algorithm addresses these by providing a mathematically rigorous framework that is computationally efficient.
Proposed Method: FDL_PG
The FDL_PG algorithm optimizes the following objective function: $$\min_{D,Y} \frac{1}{2} \|DY - X\|_F^2 + \lambda \|Y\|_1 \text{ s.t. } \|d_i\|_2 \le 1$$
Key innovations include:
- Proximal Gradient Descent: Replaces complex matrix inversions with gradient steps followed by proximal operators (soft-thresholding for sparsity and projection for dictionary constraints).
- Extrapolation (Momentum): Utilizes an extrapolation weight ($\omega$), similar to the FISTA approach, to accelerate convergence.
- Combined Optimization: Reduces iterative overhead by using a combined strategy for updating the dictionary and coefficients simultaneously.
- Theoretical Convergence: Leverages the Kurdyka-Łojasiewicz (KL) property to guarantee global convergence to a stable point.
Experimental Setup
The algorithm was validated using synthetic datasets under controlled conditions:
- Training Data ($X$): $n$-dimensional space ($n=36$).
- Dictionary ($D$): Random matrix $D \in R^{n \times K}$ with $K = 2n$ or $4n$.
- Sparsity ($r$): Signals formed from $r$ atoms ($r \in [4, 12]$).
- Sample Size ($p$): Training signals set to $20n$ or $100n$.
Results and Discussion
FDL_PG demonstrates clear dominance in efficiency and robustness. As shown in the experimental results for limited training data ($p=20n$), FDL_PG is significantly faster than its counterparts.
Key findings include:
- Significant Speedup: For $K=2n, p=20n, r=4$, FDL_PG took only 0.676 seconds, nearly 40x faster than K-SVD (28.8s) and 8x faster than OLM (5.6s).
- Robustness to Sparsity: While K-SVD's recovery accuracy drops to 0% as signals become less sparse ($r \ge 8$), FDL_PG maintains accuracies above 94%.
- Data Efficiency: The algorithm performs exceptionally well even with limited training samples ($p=20n$), making it more practical for scenarios where data is scarce.
Conclusion
The FDL_PG algorithm successfully bridges the gap between theoretical rigor and computational speed in dictionary learning. By utilizing proximal gradient methods and extrapolation, it achieves orders-of-magnitude speedups over K-SVD while ensuring global convergence. Future work will focus on applying this framework to real-world high-dimensional signal processing tasks and refining parameter tuning for unknown signal structures.
Summary updated