臺灣博碩士論文加值系統

壓縮感知打破傳統採樣定理的瓶頸。壓縮感知理論充分利用信號的稀疏性，能夠從少量的觀測值中重構出原始信號。它能解決採樣設備的設計瓶頸，節省儲存與傳輸成本。
稀疏信號重構(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.

中文摘要 I
Abstract III
Acknowledgements V
Table of Contents VI
List of Tables VIII
List of Figures IX
Chapter 1 Introduction 1
1.1 Research Background 1
1.2 The Recent Development of CS 2
1.3 The Contents and the Major Contributions of the dissertation 4
Chapter 2 Compressed Sensing 7
2.1 The Introduction of CS Theory 7
2.2 Sparse Representation of the Signal 8
2.3 Design of Measurement Matrix 10
2.4 Research of Reconstruction Algorithms 13
Chapter 3 Sparse Reconstruction Algorithm Based on Norm Minimization 19
3.1 Introduction of MP and OMP Algorithm 19
3.2 The Proposed GASAMP Algorithm 24
3.3 Simulation Results and Analysis 30
Chapter 4 Fuzzy Rules Reduction Through LARS Algorithm 36
4.1 Fuzzy Inference System 36
4.2 The Rules Reduction Algorithm Based on the LARS Algorithm 40
Chapter 5 Conclusion and Future Work 58
5.1 Conclusion 58
5.2 Future Work 59
References 61
Table 1 The comparison of the different model 53
Table 2 The performance comparison of different model 56
Figure 1 Sampling and transmission process of CS signal 8
Figure 2 SAMP algorithm 26
Figure 3 GASAMP algorithm 27
Figure 4 Probability of exact recovery vs the number of measurements 32
Figure 5 Average running time vs the number of measurement value 32
Figure 6 Probability of exact recovery vs the number of sparsity level K 33
Figure 7 Average running time vs sparsity level K 34
Figure 8 Probability of exact recovery vs length of signal 35
Figure 9 Average running time vs length of signal 35
Figure 10 Fuzzy inference system 36
Figure 11 The geometric principle of LARS 44
Figure 12 Architecture of the proposed model 47
Figure 13 The comparison of the model output and the actual data 52
Figure 14 MAE comparison between the model output and the actual data 52
Figure 15 The selection process of fuzzy rules through LARS 55
Figure 16 The ten steps of rules added 55
Figure 17 The comparison of model output and actual data. 56

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.
6.D. Baron, M. F. Duarte, M. B. Wakin, S. Sarvotham, and R. G. Baraniuk (2009), "Distributed compressive sensing," arXiv preprint arXiv:0901.3403,
7.S. Ji and L. Carin (2007), "Bayesian Compressive Sensing and Projection Optimization," Proceedings of the Proceedings of the 24th international conference on Machine learning, pp. 377-384.
8.R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde (2010), "Model-Based Compressive Sensing," IEEE Transactions on Information Theory, Vol. 56, No. 4, pp. 1982-2001.
9.R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin (2008), "A Simple Proof of the Restricted Isometry Property for Random Matrices," Constructive Approximation, Vol. 28, No. 3, pp. 253-263.
10.E. J. Candes and T. Tao (2005), "Decoding by linear programming," IEEE Transactions on Information Theory, Vol. 51, No. 12, pp. 4203-4215.
11.G. Chen, A. V. Little, M. Maggioni, and L. Rosasco (2011), "Some Recent Advances in Multiscale Geometric Analysis of Point Clouds", in Wavelets and Multiscale Analysis: Theory and Applications, J. Cohen and A. I. Zayed (Eds.), Birkhäuser Boston: Boston, pp. 199-225.
12.X. Gao, W. Lu, D. Tao, and X. Li (2009), "Image Quality Assessment Based on Multiscale Geometric Analysis," IEEE Transactions on Image Processing, Vol. 18, No. 7, pp. 1409-1423.
13.A. V. Little, M. Maggioni, and L. Rosasco (2017), "Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature," Applied and Computational Harmonic Analysis, Vol. 43, No. 3, pp. 504-567.
14.K. K. Herrity, A. C. Gilbert, and J. A. Tropp (2006), "Sparse Approximation Via Iterative Thresholding," Proceedings of the 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, pp. 624-627.
15.L. Peotta, L. Granai, and P. Vandergheynst (2006), "Image compression using an edge adapted redundant dictionary and wavelets," Signal Processing, Vol. 86, No. 3, pp. 444-456.
16.E. J. Candes, Y. C. Eldar, D. Needell, and P. Randall (2011), "Compressed Sensing with Coherent and Redundant Dictionaries," Applied and Computational Harmonic Analysis, Vol. 31, No. 1, pp. 59-73.
17.D. L. Donoho, I. Johnstone, and A. Montanari (2013), "Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising," IEEE Transactions on Information Theory, Vol. 59, No. 6, pp. 3396-3433.
18.Y. Sun, G. Gu, X. Sui, Y. Liu, and C. Yang (2015), "Single Image Super-Resolution Using Compressive Sensing With a Redundant Dictionary," IEEE Photonics Journal, Vol. 7, No. 2, pp. 1-11.
19.L. Shao, R. Yan, X. Li, and Y. Liu (2014), "From Heuristic Optimization to Dictionary Learning: A Review and Comprehensive Comparison of Image Denoising Algorithms," IEEE Transactions on Cybernetics, Vol. 44, No. 7, pp. 1001-1013.
20.Y. Yan, Y. Yang, D. Meng, G. Liu, W. Tong, A. G. Hauptmann, et al. (2015), "Event Oriented Dictionary Learning for Complex Event Detection," IEEE Transactions on Image Processing, Vol. 24, No. 6, pp. 1867-1878.
21.I. F. Gorodnitsky and B. D. Rao (1997), "Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm," IEEE Transactions on Signal Processing, Vol. 45, No. 3, pp. 600-616.
22.E. J. Candès, J. K. Romberg, and T. Tao (2006), "Stable signal recovery from incomplete and inaccurate measurements," Communications on Pure and Applied Mathematics, Vol. 59, No. 8, pp. 1207-1223.
23.T. Strohmer and R. W. Heath (2003), "Grassmannian frames with applications to coding and communication," Applied and Computational Harmonic Analysis, Vol. 14, No. 3, pp. 257-275.
24.D. L. Donoho and M. Elad (2003), "Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization," Proceedings of the National Academy of Sciences, Vol. 100, No. 5, pp. 2197-2202.
25.S. G. Mallat and Z.Zhang (1993), "Matching Pursuits with Time-Frequency Dictionaries," IEEE Transactions on Signal Processing, Vol. 41, No. 12, pp. 3397-3415.
26.Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad (1993), "Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition," Proceedings of the Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, pp. 40-44.
27.D. L. Donoho, Y. Tsaig, I. Drori, and J. Starck (2012), "Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit," IEEE Transactions on Information Theory, Vol. 58, No. 2, pp. 1094-1121.
28.D. Needell and R. Vershynin (2010), "Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit," IEEE Journal of Selected Topics in Signal Processing, Vol. 4, No. 2, pp. 310-316.
29.D. Needell and J. A. Tropp (2009), "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples," Applied and Computational Harmonic Analysis, Vol. 26, No. 3, pp. 301-321.
30.W. Dai and O. Milenkovic (2008), "Subspace Pursuit for Compressive Sensing Signal Reconstruction," IEEE Transactions on Information Theory, Vol. 55, No. 5, pp. 2230-2249.
31.B. Varadarajan, S. Khudanpur, and T. D. Tran (2011), "Stepwise Optimal Subspace Pursuit for Improving Sparse Recovery," IEEE Signal Processing Letters, Vol. 18, No. 1, pp. 27-30.
32.V. M. Tikhomirov (1990), "Convex Analysis", in Analysis II: Convex Analysis and Approximation Theory, R. V. Gamkrelidze (Ed.), Springer Berlin Heidelberg: Berlin, Heidelberg, pp. 1-92.
33.S. Chen, D. Donoho, and M. Saunders (2001), "Atomic Decomposition by Basis Pursuit," SIAM Journal on Scientific Computing, Vol. 20, No. 1
34.M. R. Osborne and B. Presnell (1999), "A New Approach to Variable Selection in Least Squares Problems," IMA Journal of Numerical Analysis, Vol. 20, No. 3, pp. 389-403.
35.B. Efron, T. Hastie, L. Johnstone, and R. Tibshirani (2004), "Least Angle Regression," The Annals of Statistics, Vol. 32, No. 2, pp. 407-451.
36.E. Hale, W. Yin, and Y. Zhang (2008), "Fixed-Point Continuation for l1-Minimization: Methodology and Convergence," SIAM Journal on Optimization, Vol. 19, No. 3, pp. 1107-1130.
37.M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright (2007), "Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems," IEEE Journal of Selected Topics in Signal Processing, Vol. 1, No. 4, pp. 586-597.
38.T. Wu and K. Lange (2008), " Coordinate descent algorithms for Lasso penalized regression," The Annals of Applied Statistics, Vol. 2, No. 1, pp. 224-244.
39.Y. Li and S. Osher (2009), "Coordinate Descent Optimization for ℓ 1 Minimization with Application to Compressed Sensing:a Greedy Algorithm," Inverse Problems and Imaging, Vol. 3, No. 3, pp. 487-503.
40.P. Tseng and S. Yun (2009), "A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization," Mathematical Programming, Vol. 117, No. 1, pp. 387-423.
41.D. Tikk, P. Baranyi, and R. Patton (2008), "Approximation properties of TP forms and its consequences to TPDC design framework," Asian Journal of Control, Vol. 9, pp. 221-231.
42.D. Li, Q. Wang, and Y. Shen (2015), "Intelligent greedy pursuit model for sparse reconstruction based on l0 minimization," Signal Processing, Vol. 122
43.H. Liu, G. Hua, H. Yin, and Y. Xu (2018), "An Intelligent Grey Wolf Optimizer Algorithm for Distributed Compressed Sensing," Computational Intelligence and Neuroscience, Vol. 2018, pp. 1-10.
44.X. Du, L. Cheng, and D. Chen (2014), "A simulated annealing algorithm for sparse recovery by l0 minimization," Neurocomputing, Vol. 131, No. 9, pp. 98–104.
45.X. Du, L. Cheng, and G. Cheng (2014), "A heuristic search algorithm for the multiple measurement vectors problem," Signal Processing, Vol. 100, No. 5, pp. 1-8.
46.M. H. Conde and O. Loffeld (2017), "A genetic algorithm for compressive sensing sparse recovery," Proceedings of the 2017 IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), pp. 106-111.
47.Z. Lin (2012), "Image adaptive recovery based on compressive sensing and genetic algorithm," Proceedings of the 2012 IEEE International Conference on Computer Science and Automation Engineering (CSAE), pp. 346-349.
48.G. Davis, S. Mallat, and Z. F. Zhang (1994), "Adaptive time-frequency decompositions," Optical Engineering, Vol. 33, No. 2
49.T. Cai and L. Wang (2011), "Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise," IEEE Transactions on Information Theory, Vol. 57, pp. 4680-4688.
50.T. T. Do, L. Gan, N. Nguyen, and T. D. Tran (2008), "Sparsity adaptive matching pursuit algorithm for practical compressed sensing," Proceedings of the 2008 42nd Asilomar Conference on Signals, Systems and Computers, pp. 581-587.
51.S. Poles, F. Yan, and E. Rigoni (2009), The Effect of Initial Population Sampling on the Convergence of Multi-Objective Genetic Algorithms: Springer Berlin Heidelberg.
52.M.-T. Su, C.-H. Chen, C.-J. Lin, and C.-T. Lin (2011), "A Rule-Based Symbiotic Modified Differential Evolution for Self-Organizing Neuro-Fuzzy Systems," Applied Soft Computing, Vol. 11, No. 8, pp. 4847-4858.
53.X. Hu, S. Li, and Y. Yang (2015), "Advanced Machine Learning Approach for Lithium-Ion Battery State Estimation in Electric Vehicles," IEEE Transactions on Transportation Electrification, Vol. 2, No. 2, pp. 140-149.
54.J. J. Buckley (1993), "Sugeno type controllers are universal controllers," Fuzzy Sets and Systems, Vol. 53, No. 3, pp. 299-303.
55.J. Castro (1995), "Fuzzy Logic Controllers Are Universal Approximators," IEEE Transactions on Systems, Man, and Cybernetics, Vol. 25, pp. 629-635.
56.B. Kosko (1994), "Fuzzy Systems as Universal Approximators," IEEE Transactions on Computers, Vol. 43, pp. 1329-1333.
57.E. D. Lughofer (2008), "FLEXFIS: A Robust Incremental Learning Approach for Evolving Takagi–Sugeno Fuzzy Models," IEEE Transactions on Fuzzy Systems, Vol. 16, No. 6, pp. 1393-1410.
58.C. C. Chen and C. C. Wong (2005), "Significant fuzzy rules extraction by an SVD-QR-based approach," Cybernetics and Systems, Vol. 36, pp. 597-622.
59.O. Kaynak (2001), "A novel optimization procedure for training of fuzzy inference systems by combining variable structure systems technique and Levenberg–Marquardt algorithm," Fuzzy Sets and Systems, Vol. 122, pp. 153-165.
60.R. Ji, Y. Yang, and W. Zhang (2013), "TS-fuzzy modeling based on ε-insensitive smooth support vector regression," Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, Vol. 24, pp. 805-817.
61.G. Mendez, J. Martinez, D. González-González, and F. Rendón-Espinoza (2014), "Orthogonal-least-squares and backpropagation hybrid learning algorithm for interval A2-C1 singleton type-2 Takagi-Sugeno-Kang fuzzy logic systems," International Journal of Hybrid Intelligent Systems, Vol. 11, pp. 125-135.
62.L.-X. Wang (1999), "Analysis and design of hierarchical fuzzy systems," IEEE Transactions on Fuzzy Systems, Vol. 7, pp. 617-624.
63.J. Yen and L. Wang (1999), "Simplifying Fuzzy Rule-based Models Using Orthogonal Transformation Methods," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, Vol. 29, pp. 13-24.
64.S. Jakubek, C. Hametner, and N. Keuth (2008), "Total least squares in fuzzy system identification: An application to an industrial engine," Engineering Applications of Artificial Intelligence, Vol. 21, No. 8, pp. 1277-1288.
65.S. Destercke, S. Guillaume, and B. Charnomordic (2008), "Building an interpretable fuzzy rule base from data using Orthogonal Least Squares—Application to a depollution problem," Fuzzy Sets and Systems, Vol. 158, pp. 2078-2094.
66.L. Szeidl and P. Várlaki (2009), "HOSVD Based Canonical Form for Polytopic Models of Dynamic Systems," Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 13, pp. 52-60.
67.P. Baranyi, L. Koczy, and T. Gedeon (2005), "A Generalized Concept for Fuzzy Rule Interpolation," IEEE Transactions on Fuzzy Systems,, Vol. 12, pp. 820-837.
68.D. Tikk and P. Baranyi (2000), "Comprehensive Analysis of a New Fuzzy Rule Interpolation Method," IEEE Transactions on Fuzzy Systems, Vol. 8, pp. 281-296.
69.H. Ishibuchi, K. Nozaki, N. Yamamoto, and H. Tanaka (1995), "Selecting fuzzy if-then rules for classification problems using genetic algorithms," IEEE Transactions on Fuzzy Systems, Vol. 3, No. 3, pp. 260-270.
70.O. Cordón, M. J. del Jesus, F. Herrera, and M. Lozano (1999), "MOGUL: A methodology to obtain genetic fuzzy rule-based systems under the iterative rule learning approach," International Journal of Intelligent Systems, Vol. 14, No. 11, pp. 1123-1153.
71.A. Eiben (2004), "Introduction to Evolutionary Computing20041 Introduction to Evolutionary Computing," Assembly Automation, Vol. 24, pp. 324-324.
72.O. Cordon and F. Herrera (1997), "A three-stage process for learning descriptive and approximate fuzzy logic controller knowledge bases from examples," International Journal of Approximate Reasoning, Vol. 17, pp. 369-407.
73.M. Antonelli, P. Ducange, and F. Marcelloni (2014), "A fast and efficient multi-objective evolutionary learning scheme for fuzzy rule-based classifiers," Information Sciences, Vol. 283, pp. 36-54.
74.C.-F. Juang, T.-L. Jeng, and Y.-C. Chang (2016), "An Interpretable Fuzzy System Learned Through Online Rule Generation and Multiobjective ACO With a Mobile Robot Control Application," IEEE Transactions on Cybernetics, Vol. 46, No. 12, pp. 2706-2718.
75.L.-C. Duţu, G. Mauris, and P. Bolon (2018), "A Fast and Accurate Rule-Base Generation Method for Mamdani Fuzzy Systems," IEEE Transactions on Fuzzy Systems, Vol. 26, No. 2, pp. 715-733.
76.M. Luo, F. Sun, and H. Liu (2013), "Hierarchical Structured Sparse Representation for T–S Fuzzy Systems Identification," IEEE Transactions on Fuzzy Systems, Vol. 21, pp. 1032-1043.
77.J. Tropp (2004), "Greed is Good: Algorithmic Results for Sparse Approximation," IEEE Transactions on Information Theory, Vol. 50, pp. 2231-2242.
78.D. Donoho (2006), "For most large underdetermined systems of equations, the minimal " Communications on Pure and Applied Mathematics, Vol. 59, pp. 907-934.
79.D. L. Donoho and Y. Tsaig (2008), "Fast Solution of l1-Norm Minimization Problems When the Solution May Be Sparse," IEEE Transactions on Information Theory, Vol. 54, No. 11, pp. 4789-4812.
80.R. Tibshirani (1996), "Regression Shrinkage and Selection Via the Lasso," Journal of the Royal Statistical Society: Series B (Methodological), Vol. 58, No. 1, pp. 267-288.