nips nips2011 nips2011-270 nips2011-270-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, Hisashi Kashima
Abstract: We analyze the statistical performance of a recently proposed convex tensor decomposition algorithm. Conventionally tensor decomposition has been formulated as non-convex optimization problems, which hindered the analysis of their performance. We show under some conditions that the mean squared error of the convex method scales linearly with the quantity we call the normalized rank of the true tensor. The current analysis naturally extends the analysis of convex low-rank matrix estimation to tensors. Furthermore, we show through numerical experiments that our theory can precisely predict the scaling behaviour in practice.
[1] E. Acar and B. Yener. Unsupervised multiway data analysis: A literature survey. IEEE T. Knowl. Data. En., 21(1):6–20, 2009.
[2] F.R. Bach. Consistency of trace norm minimization. J. Mach. Learn. Res., 9:1019–1048, 2008.
[3] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[4] R. Bro. PARAFAC. Tutorial and applications. Chemometr. Intell. Lab., 38(2):149–171, 1997.
[5] E. J. Candes and B. Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 9(6):717–772, 2009.
[6] J.D. Carroll and J.J. Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition. Psychometrika, 35(3):283–319, 1970.
[7] P. Comon. Tensor decompositions. In J. G. McWhirter and I. K. Proudler, editors, Mathematics in signal processing V. Oxford University Press, 2002.
[8] L. De Lathauwer and J. Vandewalle. Dimensionality reduction in higher-order signal processing and rank-(r1 , r2 , . . . , rn ) reduction in multilinear algebra. Linear Algebra Appl., 391:31–55, 2004.
[9] K. Fukumizu. Generalization error of linear neural networks in unidentifiable cases. In Algorithmic Learning Theory, pages 51–62. Springer, 1999.
[10] S. Gandy, B. Recht, and I. Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27:025010, 2011.
[11] J. H˚ stad. Tensor rank is NP-complete. Journal of Algorithms, 11(4):644–654, 1990. a
[12] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.
[13] J. Liu, P. Musialski, P. Wonka, and J. Ye. Tensor completion for estimating missing values in visual data. In Prof. ICCV, 2009.
[14] M. Mørup. Applications of tensor (multiway array) factorizations and decompositions in data mining. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 1(1):24–40, 2011.
[15] S. Negahban, P. Ravikumar, M. Wainwright, and B. Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in NIPS 22, pages 1348–1356. 2009.
[16] S. Negahban and M.J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Technical report, arXiv:1009.2118, 2010.
[17] S. Negahban and M.J. Wainwright. Estimation of (near) low-rank matrices with noise and highdimensional scaling. Ann. Statist., 39(2), 2011.
[18] B. Recht, M. Fazel, and P.A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010.
[19] A. Rohde and A.B. Tsybakov. 39(2):887–930, 2011. Estimation of high-dimensional low-rank matrices. Ann. Statist.,
[20] N.D. Sidiropoulos, R. Bro, and G.B. Giannakis. Parallel factor analysis in sensor array processing. IEEE T. Signal Proces., 48(8):2377–2388, 2000.
[21] M. Signoretto, L. De Lathauwer, and J.A.K. Suykens. Nuclear norms for tensors and their use for convex multilinear estimation. Technical Report 10-186, ESAT-SISTA, K.U.Leuven, 2010.
[22] N. Srebro, J. D. M. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization. In Lawrence K. Saul, Yair Weiss, and L´ on Bottou, editors, Advances in NIPS 17, pages 1329–1336. MIT Press, Came bridge, MA, 2005.
[23] R. Tomioka, K. Hayashi, and H. Kashima. Estimation of low-rank tensors via convex optimization. Technical report, arXiv:1010.0789, 2011.
[24] L. R. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279–311, 1966.
[25] M. Vasilescu and D. Terzopoulos. Multilinear analysis of image ensembles: Tensorfaces. Computer Vision—ECCV 2002, pages 447–460, 2002.
[26] H. Wang and N. Ahuja. Facial expression decomposition. In Proc. 9th ICCV, pages 958 – 965, 2003. 9