(3.227.208.0) 您好!臺灣時間:2021/04/18 13:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳以雷
研究生(外文):Chen, Yi-Lei
論文名稱:基於流形導向之低秩張量完備化
論文名稱(外文):Manifold Guided Tensor Completion under Low-rank Structure
指導教授:許秋婷許秋婷引用關係
學位類別:博士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:79
中文關鍵詞:張量完備化張量分解低秩估計流形學習
外文關鍵詞:tensor completiontensor decompositionlow-rank approximationmanifold learning
相關次數:
  • 被引用被引用:0
  • 點閱點閱:239
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:28
  • 收藏至我的研究室書目清單書目收藏:0
本論文擬基於張量完備化技術,解決各種實際應用中常見的資料遺失問題。現有方法假定完備化後的張量具有低秩性質,因此將預測張量中的遺失資訊轉化為復原一個低秩張量。其中,張量分解與最小化張量秩是目前最為普及的兩類技術。然而若張量中遺失資訊的比例太高,前者事先定義的低秩結構一旦不夠準確,很容易造成模型的過擬合;相較之下後者雖然可以透過最佳化方式估算張量的秩,但因為沒有考慮張量的隱含結構,通常無法有效表示模型變因。我們提出一種核心概念突破既有方法的瓶頸─「同步估測張量中遺失的資訊及其隱含的內部結構」。因此我們設計了一種可以同步對張量進行分解與完備化的方法。此方法主要貢獻有三。其一,我們結合了最小化秩的最佳化技術與基於Tucker模型的分解技術,因此不但可以利用最佳化方式自動估算張量的秩,也能同時保存張量中的隱含結構。其二,以張量結構表示的真實資料通常包含豐富的語義性,因此我們另外引入低維度流形的特性來描述張量中可觀察資訊與遺失資訊之間的隱含語義關係。由於考量了隱含結構,我們可以利用模型中變因的先驗資訊進而表示這些變因在一個聯合低維度的流形分佈。最後,考量在某些實際應用中變因的先驗資訊可能無法評估,我們對提出的演算法設計一種非監督式的擴展。此擴展的演算法僅基於對流形的的平滑性質假設,估算張量結構中變因的排序結果來恢復其隱含的平滑流形。在實驗的部分,我們首先利用合成資料驗證所提出演算法的收斂性,之後將我們的方法應用至實際問題。實驗結果顯示,在數種基於張量表示的應用中(例如多變因的資料分析以及視覺資料完備化),我們的方法均大幅超越現今的張量完備化技術。
In this dissertation, we focus on tensor completion, which is closely related to the ubiquitous missing data problem in real-world applications. Given a tensor with incomplete entries, existing methods assume the desired tensor exhibits low-rank structure. Predicting missing entries then boils down to recovering a low-rank tensor from given entries. Factorization schemes and completion schemes are two popular methodologies. As the number of missing entries increases, factorization schemes overfit the model structure due to their incorrectly predefined tensor’s rank, while completion schemes fail to interpret the model factors because they solely rely on rank minimization. Therefore, we introduce a novel concept to break the current limitations: complete the missing entries and simultaneously capture the underlying model structure. We propose a method called Simultaneous Tensor Decomposition and Completion (STDC). The major contributions are three-fold. First, we leverage rank minimization with Tucker model decomposition; i.e., we automate rank estimation while carefully maintain the latent tensor structure. Second, considering the informative semantics (named factor priors in our work) of real-world tensor objects, we discover the latent manifold with a new presented methodology, called Multilinear Graph Embedding (MGE), and study its significance in tensor completion. Finally, because factor priors are task-dependent and can be unavailable, we further propose a prior-free extension with a new presented methodology, called Permutation on Manifolds (PoM), to automate joint-manifold learning. We conducted experiments to empirically verify the convergence of our algorithm on synthetic data, and evaluate its effectiveness on various kinds of real-world data. The results demonstrate the superiority of our method and its potential usage in tensor-based applications.
中文摘要 I
Abstract II
誌謝 III
Introduction 1
1.1 Overview 1
1.2 Organization and Contributions 4
Background 7
2.1 Notations and Tensor Basics 7
2.2 Factorization-based Methods 7
2.2.1 Overview 7
2.2.2 Recent Advances 10
2.3 Completion-based Methods 12
2.3.1 Overview 12
2.3.2 Recent Advances 14
2.4 Probabilistic-based Methods 16
2.5 Comparison and Motivation 19
Problem Formulation 21
3.1 Overview 21
3.1.1 Low Tensor’s Rank 22
3.1.2 Low-dimensional Manifold in Latent Factors 22
3.2 Factor Priors for Tensor Analysis 23
3.2.1 Description 23
3.2.2 Multilinear Graph Embedding 24
3.2.3 Examples 25
3.2.4 General Definition 27
3.2.5 Comparison with [36] 27
3.3 Maximum a Posteriori (MAP) Formulation 27
Main Algorithm 30
4.1 Augmented Lagrange Multiplier (ALM) method 30
4.2 Simultaneous Tensor Decomposition and Completion 31
4.2.1 Optimization of V_k 32
4.2.2 Optimization of "Z" 33
4.2.3 Optimization of "X" 34
4.2.4 Summary 35
4.3 Convergence of the STDC algorithm 36
4.4 Implementation Issues 36
4.4.1 Efficient Variants of STDC 36
4.4.2 Parameter Settings 37
4.5 Handling Noisy Observations 38
Prior-free Extension 41
5.1 Overview 41
5.2 Permutation on Manifolds 42
5.2.1 Description 42
5.2.2 Algorithm 43
5.2.3 Analysis and Evaluation 46
5.3 Prior-free STDC 48
Experiment Results 51
6.1 Validation of STDC on Synthetic Data 51
6.2 Performance Evaluation on Multifactor Data Analysis 55
6.3 Performance Evaluation on Visual Data 61
6.4 Performance Evaluation of Prior-free STDC 65
Concluding Remarks 72
Bibliography 74

[1] T. Ding, M. Sznaier, and O. I. Camps, “A rank minimization approach to video inpainting,” in Proc. the IEEE International Conference on Computer Vision (ICCV), pp. 1-8, 2007.
[2] Y. X. Wang and Y. J. Zhang, “Image inpainting via weighted sparse non-negative matrix factorization,” in Proc. the IEEE International Conference on Image Processing (ICIP), pp. 3409-3412, 2011.
[3] H. Ji, C. Liu, Z. Shen, and Y. Xu, “Robust video denoising using low rank matrix completion,” in Proc. the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1791-1798, 2010.
[4] Y. Peng, A. Ganesh, J. Wright, W. Xu, and Y. Ma, “RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 34, no.11, pp. 2233-2246, 2012.
[5] J. Y. Lee, Y. Matsushita, B. Shi, I. S. Kweon, and K. Ikeuchi, “Radiometric calibration by rank minimization,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 35, no.1, pp. 144-156, 2013.
[6] G. Ye, D. Liu, I. H. Jhuo, and S. F. Chang, “Robust late fusion with rank minimization,” in Proc. the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3021-3028, 2012.
[7] Z. Zeng, T. H. Chan, K. Jia, and D. Xu, “Finding correspondence from multiple images via sparse and low-rank decomposition,” in Proc. the European Conference on Computer Vision (ECCV), pp. 325-339, 2012.
[8] Z. Zhang, X. Liang, and Y. Ma, “Unwrapping low-rank textures on generalized cylindrical surfaces,” in Proc. the IEEE International Conference on Computer Vision (ICCV), pp. 1347-1354, 2011.
[9] Z. Zhnag, A. Ganesh, X. Liang, and Y. Ma, “TILT: transform invariant low-rank textures,” International Journal of Computer Vision, vol. 99, no.1, pp. 1-24, 2012.
[10] C. Lang, G. Liu, J. Yu, and S. Yan, “Saliency detection by multitask sparsity pursuit,” IEEE Trans. Image Processing, vol. 21, no. 3, pp. 1327-1338, 2012.
[11] L. Zhuang, H. Gao, J. Huang, and N. Yu, “Semi-supervised classification via low-rank graph,” in Proc. the IEEE International Conference on Image and Graphics (ICIG), pp. 511-516, 2011.
[12] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 35, no.1, pp. 171-184, 2013.
[13] K. Li, Q. Dai, W. Xu, and J. Jiang, “Three-dimensional motion estimation via matrix completion,” IEEE Trans. System, Man, and Cybernetics- part B: Cybernetics, vol. 42, no. 2, pp. 539-551, 2012.
[14] X. Zhou, C. Yang, and W. Yu, “Moving object detection by detecting contiguous outliers in the low-rank representation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 35, no. 3, pp. 597-610, 2013.
[15] O. Oreifej, X. Lin, and M. Shah, “Simultaneous video stabilization and moving object detection in turbulence,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 35, no. 2, pp. 450-462, 2013.
[16] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, Wiley Interscience, 2000.
[17] D. D. Lee and H. S. Seung, “Learning the parts of objects by nonnegative matrix factorization,” Nature, vol. 401, pp. 788-791, 1999.
[18] S. Ma, D. Goldfarb, and L. Chen, “Fixed point and Bregman iterative methods for matrix rank minimization,” Mathematical Programming, vol. 128, no. 1, pp. 321-353, 2009.
[19] J. F. Cai, E. J. Candes, and Z. Shen, “A singular value algorithm for matrix completion,” SIAM Journal on Optimization, vol. 20, no. 4, pp. 1956-1982, 2010.
[20] X. Lu, T. Gong, P. Yan, Y. Yuan, and X. Li, “Robust alternative minimization for matrix completion,” IEEE Trans. System, Man, and Cybernetics- part B: Cybernetics, vol. 42, no. 3, pp. 939-949, 2012.
[21] B. Recht, M. Fazel, and P. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM Review, vol. 52, no. 3, pp. 471-501, 2010.
[22] W. J. Li and D. Y. Yeung, “Relation regularized matrix factorization,” in Proc. the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1126-1131, 2009.
[23] A. D. Bue, J. Xavier, L. Agapito, and M. Paladini, “Bilinear modeling via augmented Lagrange multipliers,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 34, no. 8, pp. 1496-1508, 2012.
[24] J. Chen and Y. Saad, “On the tensor SVD and the optimal low rank orthogonal approximation of tensors,” SIAM Journal on Matrix Analysis and Applications, vol. 30, no. 4, pp. 1709-1734, 2009.
[25] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Morup, “Scalable tensor factorization for incomplete data,” Chemometrics and Intelligent Laboratory Systems, vol. 106, pp. 41-56, 2011.
[26] X. Geng, K. Smith-Miles, Z. H. Zhou, and L. Wang, “Face image modeling by multilinear subspace analysis with missing values,” IEEE Trans. System, Man, and Cybernetics- part B: Cybernetics, vol. 41, no. 3, pp. 881-892, 2011.
[27] J. Liu, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” in Proc. the IEEE International Conference on Computer Vision (ICCV), pp. 2114-2121, 2009.
[28] Y. Li, J. Yan, Y. Zhou, and J. Yang, “Optimum subspace learning and error correction for tensors,” in Proc. the European Conference on Computer Vision (ECCV), pp. 790-803, 2010.
[29] S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” Inverse Problems, vol. 27, no. 2, 2011.
[30] Y. Liu and F. Shang, “An efficient matrix factorization method for tensor completion,” IEEE Signal Processing Letters, vol. 20, no. 4, pp. 307-310, 2013.
[31] J. Liu, P. Musialski, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 35, no.1, pp. 208-220, 2013.
[32] R. Tomioka, T. Suzuki, K. Hayashi, and H. Kashima, “Statistical performance of convex tensor decomposition,” in Proc. the Annual Conference on Neural Information Processing Systems (NIPS), pp. 972-980, 2011.
[33] M. Signoretto, L .D. Lathauwer, and J. A. K. Suykens, “Nuclear norms for tensors and their use for convex multilinear estimation,” Internal Report 10-186, ESAT-SISTA, K. U. Leuven, 2010.
[34] R. P. Adams, G. E. Dahl, and I. Murray, “Incorporating side information in probabilistic matrix factorization with Guassian process,” in Proc. the Annual Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1-9, 2010.
[35] R. Salakhutdinov and A. Mnih, “Probabilistic matrix factorization,” in Proc. the Annual Conference on Neural Information Processing Systems (NIPS), pp.1257-1264, 2008.
[36] A. Narita, K. Hayashi, R. Tomioka, and H. Kashima, “Tensor factorization using auxiliary information,” in Proc. the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), pp. 501-516, 2011.
[37] D. Kressner, M. Steinlechner, and B. Vadereycken, “Low-rank tensor completion by Riemannian optimization,” SIAM Journal on Optimization, vol. 23, no. 2, pp. 1214-1236, 2013.
[38] L. D. Lathauwer, B. D. Moor, and J. Vandewalle, “A multilinear singular value decomposition,” SIAM J. on Matrix Anal. Appl., vol. 21, no. 4, pp. 1254-1278, 2000.
[39] B. Chen, Z. Li, and S. Zhang, “On tensor Tucker decomposition: the case for an adjustable core size,” Technical Report, 2013.
[40] M. E. Kilmer, K. Braman, and N. Hao, “Third order tensors as operators on matrices: a theoretical and computational framework with applications in imaging,” Tufts Computer Science Technical Report, 2011.
[41] Z. Zhang, G. Ely, S. Aeron, N. Hao, and M. Kilmer, “Novel factorization strategies for higher order tensors: implications for compression and recovery of multi-linear data,” arXiv: 1307.0805v3, 2013.
[42] S. Yan, D. Xu, B. Zhang, H. Zhang, Q. Yang, and S. Lin, “Graph embedding and extensions: a general framework for dimensionality reduction,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 40-51, 2007.
[43] J. Hastad, “Tensor rank is NP complete,” Journal of Algorithms, vol. 11, no. 4, pp. 644-654, 1990.
[44] B. Alexeev, M. A. Forbes, and J. Tsimerman, “Tensor rank: some lower and upper bounds,” in proc. IEEE Annual Conference on Computational Complexity (CCC), pp. 283-291, 2011.
[45] P. Burgisser and C. Ikenmeyer, “Geometric complexity theory and tensor rank,” in Proc. Annual ACM Symposium on Theory of Computing, pp. 509-518, 2011.
[46] V. De Silva and L. H. Lim, “Tensor rank and the ill-posedness of the best low-rank approximation problem,” SIAM Journal on Matrix Analysis and Applications, vol. 30, no. 3, pp. 1084-1127, 2008.
[47] B. Romera-Paredes and M. Pontil, “A new convex relaxation for tensor completion,” arXiv:1307.4653, 2013.
[48] M. Al-Qizwini and H. Radha, “Fast smooth rank approximation for tensor completion,” in the 48th Annual Conference on Information Science and Systems (CISS), 2014.
[49] K. Mohan and M. Fazel, “Iterative reweighted algorithms for matrix rank minimization,” Journal of Machine Learning Research (JMLR), vol. 13, pp. 3441-3473, 2012.
[50] J. Geng, L. Wang, Y. Xu, and X. Wang, “A weighted nuclear norm method for tensor completion,” International Journal of Signal Processing, Image Processing, and Pattern Recognition, vol. 7, no. 1, pp. 1-12, 2014.
[51] K. Mohan and M. Fazel, “Reweighted nuclear norm minimization with application to system identification,” American Control Conference (ACC), pp. 2953-2959, 2010.
[52] C. Mu, B. Huang, J. Wright, and D. Goldfarb, “Square deal: lower bounds and improved relaxations for tensor recovery,” arXiv:1307.5870, 2013.
[53] W. Chu and Z. Ghahramani, “Probabilistic models for incomplete multi-dimensional arrays,” in Proc. JMLR Workshops and Conference, vol. 5, pp. 89-96, 2009.
[54] L. Xiong, X. Chen, T. K. Huang, J. Schneider, and J. G. Carbonell, “Temporal collaborative filtering with Bayesian probabilistic tensor factorization,” in Proc. SIAM Data Mining, 2010.
[55] S. Gao, L. Denoyer, P. Gallinari, and J. Guo, “Probabilistic latent tensor factorization model for link pattern prediction in multi-relational networks,” The Journal of China Universities of Posts and Telecommunications, vol. 19, pp. 172-181, 2012.
[56] K. Hayashi, T. Takenouchi, T. Shibata, Y. Kamiya, D. Kato, K. Kunieda, K. Yamada, and K. Ikeda, “Exponential family tensor factorization for missing-values prediction and anomaly detection,” in Proc. IEEE Conference on Data Mining (ICDM), pp. 216-225, 2010.
[57] Z. Xu, F. Yan, and A. Qi, “Infinite Tucker decomposition: nonparametric Bayesian model for multiway data analysis,” in Proc. IEEE Conference on Machine Learning (ICML), pp.1023-1030, 2012.
[58] Q. Zhao, L. Zhang, and A. Cichocki, “Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination,” CoRR abs/1401.6497, 2014.
[59] Y. L. Chen, C. T. Hsu, and H. Y. Mark Liao, “Simultaneous Tensor Decomposition and Completion Using Factor Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 36, no. 3, pp. 577-591, 2014.
[60] Y. L. Chen and C. T. Hsu, “Multilinear Graph Embedding: Representation and Regularization for Images,” IEEE Trans. Image Processing, vol. 23, no. 2, pp. 741-754, 2014.
[61] R. A. Horn and C. R. Johnson, Topic in Matrix Analysis, Cambridge University Press, 1991.
[62] T. Sim, S. Baker, and M. Bsat, “The CMU pose, illumination, and expression database,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no.12, pp.1615-1618, 2003.
[63] D. Bertsekas, Constrained Optimization and Lagrange Multiplier Method, Academic Press, 1982.
[64] Z. Lin, M. Chen, L. Wu, and Y. Ma, “The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices,” UIUC Technical Report UILU-ENG-09-2215, Technical Report, 2009.
[65] B. He, M. Tao, and X. Yuan, “Alternating direction method with Gaussian back subsititution for separable convex programming,” SIAM Journal on Optimization, vol. 22, no. 2, pp. 313-340, 2012.
[66] Y. Shen, Z. Wen, and Y. Zhang, “Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization,” Tech. Report, 2011.
[67] G. Liu and S. Yan, “Active subspace: Towards scalable low-rank learning,” Neural Computing, vol. 24, no. 12, 2012.
[68] J. Yang and X. Yuan, “Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization,” Mathematics of Computation, vol. 82, pp. 301-329, 2013.
[69] R. E. Burkard, E. Cela, P. M. Pardalos, and L. S. Pitsoulis, “The quadratic assignment problem,” SFB-Report 126, Inst. Mathematik B, Tech. Univ. Graz, Austria, 1998.
[70] P. M. Pardalos, K. G. Ramakrishnan, M. G. C. Resende, and Y. Li, “Implementation of a variable reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem,” SIAM J. Optimization, vol. 7, pp. 280-294, 1997.
[71] M. S. Bazaraa and H. D. Sherali, “On the use of exact and heuristic cutting plane methods for the quadratic assignment problem,” J. Operation Research Society, vol. 33, pp. 991-1003, 1982.
[72] K. M. Anstreicher and N. W. Brixius, “A new bound for the quadratic assignment problem based on convex quadratic programming,” Mathematical Programming, vol. 89, pp. 341-357, 2001.
[73] Y. Xia, “Second order cone programming relaxation for the quadratic assignment problem,” J. Optimization Methods and Software, vol. 23, pp. 441-449, 2008.
[74] C. Schellewald, S. Roth, and C. Schnorr, “Evaluation of a convex relaxation to a quadratic assignment matching approach for relational object views,” J. Image and Vision Computing, vol. 25, pp. 1301-1314, 2007.
[75] G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, Wiley, 1988.
[76] Z. Y. Liu and H. Qiao, “Graduated nonconvexity and concavity procedure for partial graph matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, accepted.
[77] M. Turk and A. Pentland, “Face recognition using eigenfaces,” in Proc. the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 586-591, 1991.
[78] X. He, S. Yan, Y. Hu, P. Niyogi, and H. Zhang, “Face recognition using laplacianfaces,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no.3 , pp.328-340, 2005.
[79] P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, “Eigenfaces vs. fisherfaces: recognition using class specific linear projection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 7, pp. 711-720, 1997.
[80] The FG-NET Aging database http://www.fgnet.rsunit.com/.
[81] P. Lucey, J. F. Cohm, T. Kanade, J. Saragih, Z. Ambadar, and I. Matthews, “The extended Cohn-Kanade dataset (CK+): a complete expression dataset for action unit and emotion-specified expressions,” in Proc. the IEEE International Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 94-101, 2010. .
[82] T. F. Cootes, G. J. Edwards, and C. J. Taylor, “Active appearance models,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 6, pp. 681-685, 2001.
[83] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Processing, vol. 13, no. 4, pp. 600-612, 2004.
[84] S. H. Chan, R. Khoshabeh, K. B. Gibson, P. E. Gill, and T. Q. Nguyen, “An augmented lagrangian method for total variation video restoration,” IEEE Trans. Image Processing, vol. 20, no. 11, pp. 3097-3111,2011.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔