Robust tensor CUR decompositions: rapid low-Tucker-rank tensor recovery with sparse corruptions. (English) Zbl 07851430
Summary: We study the tensor robust principal component analysis (TRPCA) problem, a tensorial extension of matrix robust principal component analysis, which aims to split the given tensor into an underlying low-rank component and a sparse outlier component. This work proposes a fast algorithm, called robust tensor CUR decompositions (RTCUR), for large-scale nonconvex TRPCA problems under the Tucker rank setting. RTCUR is developed within a framework of alternating projections that projects between the set of low-rank tensors and the set of sparse tensors. We utilize the recently developed tensor CUR decomposition to substantially reduce the computational complexity in each projection. In addition, we develop four variants of RTCUR for different application settings. We demonstrate the effectiveness and computational advantages of RTCUR against state-of-the-art methods on both synthetic and real-world datasets.
MSC:
| 62H25 | Factor analysis and principal components; correspondence analysis |
Keywords:
tensor CUR decomposition; robust tensor principal component analysis; low-rank tensor recovery; outlier detectionSoftware:
tproductReferences:
| [1] | Abdi, H. and Williams, L. J., Principal component analysis, Wiley Interdiscip. Rev. Comput. Stat., 2 (2010), pp. 433-459. |
| [2] | Bergqvist, G. and Larsson, E. G., The higher-order singular value decomposition: Theory and an application [lecture notes], IEEE Signal Process. Mag., 27 (2010), pp. 151-154. |
| [3] | Bouwmans, T., Javed, S., Zhang, H., Lin, Z., and Otazo, R., On the applications of robust PCA in image and video processing, Proc. IEEE, , 106 (2018), pp. 1427-1457. |
| [4] | Bouwmans, T., Maddalena, L., and Petrosino, A., Scene background initialization: A taxonomy, Pattern Recognit. Lett., 96 (2017), pp. 3-11. |
| [5] | Cai, H., Cai, J.-F., Wang, T., and Yin, G., Accelerated structured alternating projections for robust spectrally sparse signal recovery, IEEE Trans. Signal Process., 69 (2021), pp. 809-821. · Zbl 1543.94083 |
| [6] | Cai, H., Cai, J.-F., and Wei, K., Accelerated alternating projections for robust principal component analysis, J. Mach. Learn. Res., 20 (2019), pp. 685-717. · Zbl 1483.62098 |
| [7] | Cai, H., Cai, J.-F., and You, J., Structured gradient descent for fast robust low-rank Hankel matrix completion, SIAM J. Sci. Comput., 45 (2023), pp. 1172-1198. · Zbl 1516.65033 |
| [8] | Cai, H., Chao, Z., Huang, L., and Needell, D., Fast robust tensor principal component analysis via Fiber CUR decomposition, in Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, , IEEE, New York, 2021, pp. 189-197. |
| [9] | Cai, H., Hamm, K., Huang, L., Li, J., and Wang, T., Rapid robust principal component analysis: CUR accelerated inexact low rank estimation, IEEE Signal Process. Lett., 28 (2020), pp. 116-120. |
| [10] | Cai, H., Hamm, K., Huang, L., and Needell, D., Mode-wise tensor decompositions: Multi-dimensional generalizations of CUR decompositions, J. Mach. Learn. Res., 22 (2021), pp. 1-36. · Zbl 07415128 |
| [11] | Cai, H., Hamm, K., Huang, L., and Needell, D., Robust CUR decomposition: Theory and imaging applications, SIAM J. Imaging Sci., 14 (2021), pp. 1472-1503. · Zbl 1538.65107 |
| [12] | Cai, H., Liu, J., and Yin, W., Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection, preprint, arXiv:2110.05649, 2021. |
| [13] | Cai, J.-F., Li, J., and Xia, D., Generalized low-rank plus sparse tensor estimation by fast Riemannian optimization, J. Amer. Statist. Assoc., (2022), doi:10.1080/01621459.2022.2063131. · Zbl 07784931 |
| [14] | Caiafa, C. F. and Cichocki, A., Generalizing the column-row matrix decomposition to multi-way arrays, Linear Algebra Appl., 433 (2010), pp. 557-573. · Zbl 1194.15025 |
| [15] | Candes, E. and Romberg, J., Sparsity and incoherence in compressive sampling, Inverse Problems, 23 (2007), 969. · Zbl 1120.94005 |
| [16] | Candès, E. J., Li, X., Ma, Y., and Wright, J., Robust principal component analysis?, J. ACM, 58 (2011), pp. 1-37. · Zbl 1327.62369 |
| [17] | Carroll, J. D. and Chang, J.-J., Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition, Psychometrika, 35 (1970), pp. 283-319. · Zbl 0202.19101 |
| [18] | Chambua, J., Niu, Z., Yousif, A., and Mbelwa, J., Tensor factorization method based on review text semantic similarity for rating prediction, Expert Syst. Appl., 114 (2018), pp. 629-638. |
| [19] | Chandrasekaran, V., Sanghavi, S., Parrilo, P. A., and Willsky, A. S., Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim., 21 (2011), pp. 572-596. · Zbl 1226.90067 |
| [20] | Chao, Z., Huang, L., and Needell, D., HOSVD-based algorithm for weighted tensor completion, J. Imaging, 7 (2021), p. 110. |
| [21] | Chen, J. and Saad, Y., On the tensor SVD and the optimal low rank orthogonal approximation of tensors, SIAM J. Matrix Anal. Appl., 30 (2009), pp. 1709-1734. · Zbl 1184.65043 |
| [22] | De Lathauwer, L., De Moor, B., and Vandewalle, J., On the best rank-1 and rank-\((r_1,\ldots, r_n)\) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324-1342. · Zbl 0958.15026 |
| [23] | Dong, H., Tong, T., Ma, C., and Chi, Y., Fast and provable tensor robust principal component analysis via scaled gradient descent, Inf. Inference, 12 (2023), iaad019. · Zbl 07858360 |
| [24] | Goreĭnov, S. A., Zamarashkin, N. L., and Tyrtyshnikov, E. E., Pseudo-skeleton approximations, Dokl. Akad. Nauk, 343 (1995), pp. 151-152. |
| [25] | Gu, Q., Gui, H., and Han, J., Robust tensor decomposition with gross corruption, Adv. Neural Inform. Process. Syst., 27 (2014), pp. 1422-1430. |
| [26] | Hamm, K. and Huang, L., Perspectives on CUR decompositions, Appl. Comput. Harmon. Anal., 48 (2020), pp. 1088-1099. · Zbl 1432.15014 |
| [27] | Hamm, K. and Huang, L., Stability of sampling for CUR decompositions, Found. Data Sci., 2 (2020), 83. |
| [28] | Hamm, K., Meskini, M., and Cai, H., Riemannian CUR decompositions for robust principal component analysis, in Topological, Algebraic and Geometric Learning Workshops 2022, PMLR, Cambridge, MA, 2022, pp. 152-160. |
| [29] | Hitchcock, F. L., Multiple invariants and generalized rank of a \(p\)-way matrix or tensor, J. Math. Phys., 7 (1928), pp. 39-79. · JFM 53.0097.01 |
| [30] | Hu, Y., Liu, J.-X., Gao, Y.-L., and Shang, J., DSTPCA: Double-sparse constrained tensor principal component analysis method for feature selection, IEEE/ACM Trans. Comput. Biol. Bioinform., 18 (2021), pp. 1481-1491. |
| [31] | Hu, Y. and Work, D. B., Robust tensor recovery with fiber outliers for traffic events, ACM Trans. Knowledge Discovery Data, 15 (2020), pp. 1-27. |
| [32] | Huang, B., Mu, C., Goldfarb, D., and Wright, J., Provable low-rank tensor recovery, Optim. Online, 4252 (2014), pp. 455-500. |
| [33] | Ji, P. and Jin, J., Coauthorship and citation networks for statisticians, Ann. Appl. Stat., 10 (2016), pp. 1779-1812. · Zbl 1454.62541 |
| [34] | Lopez-Rubio, E., Foreground detection in video sequences with probabilistic self-organizing maps, http://www.lcc.uma.es/∼ezeqlr/fsom/fsom.html. |
| [35] | Lee, D. D. and Seung, H. S., Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), pp. 788-791. · Zbl 1369.68285 |
| [36] | Li, L., Huang, W., Gu, I. Y.-H., and Tian, Q., Statistical modeling of complex backgrounds for foreground object detection, IEEE Trans. Image Process., 13 (2004), pp. 1459-1472. |
| [37] | Li, X., Xu, D., Zhou, H., and Li, L., Tucker tensor regression and neuroimaging analysis, Statist. Biosci., 10 (2018), pp. 520-545. |
| [38] | Lin, Z. and Zhang, H., Low-Rank Models in Visual Analysis, Elsevier, New York, 2017, pp. 1-2. · Zbl 1453.68003 |
| [39] | Liu, J., Musialski, P., Wonka, P., and Ye, J., Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2012), pp. 208-220. |
| [40] | Liu, T., Yuan, M., and Zhao, H., Characterizing spatiotemporal transcriptome of the human brain via low-rank tensor decomposition, Statist. Biosci., (2022), pp. 1-29. |
| [41] | Liu, Y., Chen, L., and Zhu, C., Improved robust tensor principal component analysis via low-rank core matrix, IEEE J. Sel. Top. Signal Process., 12 (2018), pp. 1378-1389. |
| [42] | Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z., and Yan, S., Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, , IEEE, New York, 2016, pp. 5249-5257. |
| [43] | Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z., and Yan, S., Tensor robust principal component analysis with a new tensor nuclear norm, IEEE Trans. Pattern Anal. Mach. Intell., 42 (2019), pp. 925-938. |
| [44] | Lu, H., Plataniotis, K. N., and Venetsanopoulos, A. N., A survey of multilinear subspace learning for tensor data, Pattern Recognit., 44 (2011), pp. 1540-1551. · Zbl 1210.68083 |
| [45] | Luo, Y., Xin, Y., Hochberg, E., Joshi, R., Uzuner, O., and Szolovits, P., Subgraph augmented non-negative tensor factorization (SANTF) for modeling clinical narrative text, J. Amer. Med. Inform. Assoc., 22 (2015), pp. 1009-1019. |
| [46] | Mahoney, M. W., Maggioni, M., and Drineas, P., Tensor-CUR decompositions for tensor-based data, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 957-987. · Zbl 1168.65340 |
| [47] | M. Salut, M. and Anderson, D., Randomized Tensor Robust Principal Component Analysis, TechRxiv, 2022. |
| [48] | Netrapalli, P., N, N. U., Sanghavi, S., Anandkumar, A., and Jain, P., Non-convex robust PCA, in Advances in Neural Information Processing Systems, Vol. 27, MIT Press, Cambridge, MA, 2014. |
| [49] | Oh, S., Hoogs, A., Perera, A., Cuntoor, N., Chen, C.-C., Lee, J. T., Mukherjee, S., Aggarwal, J., Lee, H., Davis, L., Swears, E., Wang, X., Ji, Q., Reddy, K., Shah, M., Vondrick, C., Pirsiavash, H., Ramanan, D., Yuen, J., Torralba, A., Song, B., Fong, A., Roy-Chowdhury, A., and Desai, M., A large-scale benchmark dataset for event recognition in surveillance video, in CVPR 2011, IEEE, New York, 2011, pp. 3153-3160. |
| [50] | O’Toole, A. J., Harms, J., Snow, S. L., Hurst, D. R., Pappas, M. R., Ayyad, J. H., and Abdi, H., A video database of moving faces and people, IEEE Trans. Pattern Anal. Mach. Intell., 27 (2005), pp. 812-816. |
| [51] | Rabanser, S., Shchur, O., and Günnemann, S., Introduction to Tensor Decompositions and Their Applications in Machine Learning, preprint, arXiv:1711.10781, 2017. |
| [52] | Rajwade, A., Rangarajan, A., and Banerjee, A., Image denoising using the higher order singular value decomposition, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2012), pp. 849-862. |
| [53] | Sofuoglu, S. E. and Aviyente, S., A two-stage approach to robust tensor decomposition, in 2018 IEEE Statistical Signal Processing Workshop (SSP), IEEE, New York, 2018, pp. 831-835. |
| [54] | Song, T., Peng, Z., Wang, S., Fu, W., Hong, X., and Yu, P. S., Based cross-domain recommendation through joint tensor factorization, in International Conference on Database Systems for Advanced Applications, , Springer-Verlag, Berlin, 2017, pp. 525-540. |
| [55] | Tucker, L. R., Some mathematical notes on three-mode factor analysis, Psychometrika, 31 (1966), pp. 279-311. |
| [56] | Vaswani, N. and Narayanamurthy, P., Static and dynamic robust PCA and matrix completion: A review, Proc. IEEE, , 106 (2018), pp. 1359-1379. |
| [57] | Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., and Ma, Y., Robust face recognition via sparse representation, IEEE Trans. Pattern Anal. Mach. Intell., 31 (2008), pp. 210-227. |
| [58] | Xia, D., Yuan, M., and Zhang, C.-H., Statistically optimal and computationally efficient low rank tensor completion from noisy entries, Ann. Statist., 49 (2021), pp. 76-99. · Zbl 1473.62184 |
| [59] | Zhang, Z., Ely, G., Aeron, S., Hao, N., and Kilmer, M., Novel methods for multilinear data completion and de-noising based on tensor-SVD, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, , IEEE, New York, 2014, pp. 3842-3849. |
| [60] | Zheng, X., Ding, W., Lin, Z., and Chen, C., Topic tensor factorization for recommender system, Inform. Sci., 372 (2016), pp. 276-293. |
| [61] | Zhou, H., Li, L., and Zhu, H., Tensor regression with applications in neuroimaging data analysis, J. Amer. Statist. Assoc., 108 (2013), pp. 540-552. · Zbl 06195959 |
| [62] | Zhou, P., Lu, C., Lin, Z., and Zhang, C., Tensor factorization for low-rank tensor completion, IEEE Trans. Image Process., 27 (2017), pp. 1152-1163. · Zbl 1409.94796 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
