稀疏重構演算法在信號處理和模糊系統中的應用研究

The Study of the Application for Sparse Reconstruction Algorithms in Signal Processing and Fuzzy System

江慧琴(JIANG, HUIQIN)

指導教授 ： 陳榮靜

朝陽科技大學/資訊學院/資訊管理系/博士(2020年)

摘要

壓縮感知打破傳統採樣定理的瓶頸。壓縮感知理論充分利用信號的稀疏性，能夠從少量的觀測值中重構出原始信號。它能解決採樣設備的設計瓶頸，節省儲存與傳輸成本。
稀疏信號重構(Sparse Signal Reconstruciton)演算法的研究是壓縮感知(Compressed Sensing)領域一個研究熱點。根據壓縮感知理論知識，稀疏信號重構問題能轉換成基於 範數最小化約束問題。由於基於 範數約束最小化問題是NP難問題，貪婪迭代演算法被建議用來求稀疏近似解。貪婪演算法使用快速搜索策略，容易陷入局部最優解，有應用的局限性。針對以上問題，本論文提出了基因稀疏自適應匹配追蹤(Genetic Algorithm-Sparse Adaptive Matching Pursuit)演算法，該演算法結合遺傳演算法在求解組合優化問題上的優勢，以及稀疏自適應匹配追蹤演算法在快速重構方面的優勢。設置不同的步長，用稀疏自適應匹配追蹤(Sparse Adaptive Matching Pursuit)演算法產生基因演算法(Genetic Algorithm)的初始種群，再由基因演算法得到逼近最優解。通過與其它經典貪婪重構演算法的對比，該演算法有較好的信號重構率。
高維資料帶來模糊規則的資料維度指數級別的增長，“規則爆炸”成為模糊辨識系統發展的瓶頸。本論文嘗試將基於 範數約束最小化的最小角回歸(Least Angel Regression)稀疏重構演算法應用於模糊規則約簡。通過對模糊規則後件的稀疏表示，將模糊邏輯約簡問題轉化成稀疏重構問題。從實驗可以看出，與几種經典的模糊演算法相比，建議的演算法具有計算複雜度低，性能好等優點，尤其適用於高維信號。

關鍵字

壓縮感知 ； 稀疏自適應匹配追蹤演算法 ； 稀疏重構 ； 最小角回歸演算法 ； 模糊邏輯系統 ； 基因演算法

並列摘要

Compressed sensing (CS) theory has broken the bottleneck of Nyquist sampling theorem, which makes full use of the sparsity of the signal to reconstruct the signal from a small amount of measurements. It can greatly reduce the cost of signal sampling, storage and transmission.
The research of sparse reconstruction algorithms is one of the research focuses in CS theory. The sparse signal reconstruction problem can be cast as the norm minimization problem. Due to the high computational complexity of norm minimization problem, iterative greedy algorithms have been proposed to solve the sparse approximation solutions. Greedy algorithm adopts fast search strategy, which is easy to fall into local optimal solution. In view of the above problems, this dissertation proposes Genetic Algorithm Sparse Adaptive Matching Pursuit (GASAMP) algorithm, which combines the advantages of Genetic algorithm (GA) in solving combinatorial optimization problems, and the advantages of rapid reconstruction speed of greedy algorithms. The initial population of genetic algorithm is generated by Sparse Adaptive Matching Pursuit algorithm (SAMP) with different step size, and then the approximate optimal solution is obtained by genetic algorithm. Experimental results show that the proposed algorithm has good performance compared with other classical greedy algorithms.
High dimensional data brings the exponential growth of fuzzy rules, and "rules explosion" becomes the bottleneck in the development of fuzzy identification systems. In this dissertation, we also propose a rule selection-reduction algorithm based on least angle regression algorithm (LARS), which is one of sparse reconstruction algorithms based on norm minimization. By the sparse representation of fuzzy consequent parameters, redundant rules are reduced and the system is simplified. LARS algorithms makes the solving process completed in several steps. The experimental results show the algorithm has excellent performance, especially for the high-dimensional data.

並列關鍵字

Compressed Sensing ； Sparse Adaptive Matching Pursuit algorithm ； Sparse reconstruction ； Least Angel Regression algorithm ； Fuzzy Logic System ； Genetic algorithm

參考文獻

1. E. J. Candes and T. Tao (2006), "Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?," IEEE Transactions on Information Theory, Vol. 52, No. 12, pp. 5406-5425.

2. E. Lughofer and S. Kindermann (2010), "SparseFIS: Data-Driven Learning of Fuzzy Systems With Sparsity Constraints," IEEE Transactions on Fuzzy Systems, Vol. 18, No. 2, pp. 396-411.

3. D. L. Donoho (2006), "Compressed sensing," IEEE Transactions on Information Theory, Vol. 52, No. 4, pp. 1289-1306.

4. Y. Tsaig and D. L. Donoho (2006), "Extensions of compressed sensing," Signal Processing, Vol. 86, No. 3, pp. 549-571.

5. P. T. Boufounos and R. G. Baraniuk (2008), "1-Bit Compressive Sensing," Proceedings of the 2008 42nd Annual Conference on Information Sciences and Systems, pp. 16-21.