×

On norm compression inequalities for partitioned block tensors. (English) Zbl 1436.15027

Summary: When a tensor is partitioned into subtensors, some tensor norms of these subtensors form a tensor called a norm compression tensor. Norm compression inequalities for tensors focus on the relation of the norm of this compressed tensor to the norm of the original tensor. We prove that for the tensor spectral norm, the norm of the compressed tensor is an upper bound of the norm of the original tensor. This result can be extended to a general class of tensor spectral norms. We discuss various applications of norm compression inequalities for tensors. These inequalities improve many existing bounds of tensor norms in the literature, in particular tightening the general bound of the tensor spectral norm via tensor partitions. We study the extremal ratio between the spectral norm and the Frobenius norm of a tensor space, provide a general way to estimate its upper bound, and in particular, improve the current best upper bound for third order nonnegative tensors and symmetric tensors. We also propose a faster approach to estimate the spectral norm of a large tensor or matrix via sequential norm compression inequalities with theoretical and numerical evidence. For instance, the complexity of our algorithm for the matrix spectral norm is \(O\left( n^{2+\varepsilon}\right)\) where \(\varepsilon\) ranges from 0 to 1 depending on the partition and the estimate ranges correspondingly from some close upper bound to the exact spectral norm.

MSC:

15A69 Multilinear algebra, tensor calculus
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
15A45 Miscellaneous inequalities involving matrices
90C59 Approximation methods and heuristics in mathematical programming
65F55 Numerical methods for low-rank matrix approximation; matrix compression
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrachev, A., Kozhasov, K., Uschmajew, A.: Chebyshev polynomials and best rank-one approximation ratio. SIAM J. Matrix Anal. Appl. (2020) (to appear) · Zbl 1435.15019
[2] Audenaert, Kmr, A norm compression inequality for block partitioned positive definite matrices, Linear Algebra Appl., 413, 155-176 (2006) · Zbl 1092.15017
[3] Audenaert, Kmr, On a norm compression inequality for \(2\times N\) partitioned block matrices, Linear Algebra Appl., 428, 781-795 (2008) · Zbl 1171.15027
[4] Bebendorf, M., Hierarchical Matrices: A Means to Efficiently Solve Elliptic Bundary Value Problems (2008), Berlin: Springer, Berlin · Zbl 1151.65090
[5] Bennett, Ch; Shor, Pw, Quantum information theory, IEEE Trans. Inf. Theory, 44, 2724-2748 (1998) · Zbl 1099.81501
[6] Bhatia, R.; Kittaneh, F., Norm inequalities for partitioned operators and an application, Math. Ann., 287, 719-726 (1990) · Zbl 0688.47005
[7] Cai, Tt; Yuan, M., Adaptive covariance matrix estimation through block thresholding, Ann. Stat., 40, 2014-2042 (2012) · Zbl 1257.62060
[8] Chen, B.; He, S.; Li, Z.; Zhang, S., Maximum block improvement and polynomial optimization, SIAM J. Optim., 22, 87-107 (2012) · Zbl 1250.90069
[9] Chen, B.; Li, Z., On the tensor spectral \(p\)-norm and its dual norm via partitions, Comput. Optim. Appl. (2020) · Zbl 1441.15014 · doi:10.1007/s10589-020-00177-z
[10] Chen, L., Liu, Y., Zhu, C.: Iterative block tensor singular value thresholding for extraction of lowrank component of image data. In: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1862-1866 (2017)
[11] Derksen, H., On the nuclear norm and the singular value decomposition of tensors, Found. Comput. Math., 16, 779-811 (2016) · Zbl 1343.15016
[12] Friedland, S.; Lim, L-H, Nuclear norm of higher-order tensors, Math. Comput., 87, 1255-1281 (2018) · Zbl 1383.15018
[13] Gautier, A.; Tudisco, F.; Hein, M., A unifying Perron-Frobenius theorem for nonnegative tensors via multihomogeneous maps, SIAM J. Matrix Anal. Appl., 40, 1206-1231 (2019) · Zbl 07122459
[14] Golub, Gh; Van Loan, Cf, Matrix Computations (2013), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[15] Hardy, Gh; Littlewood, Je; Pólya, G., Inequalities (1934), Cambridge: Cambridge University Press, Cambridge · JFM 60.0169.01
[16] He, S.; Jiang, B.; Li, Z.; Zhang, S., Probability bounds for polynomial functions in random variables, Math. Oper. Res., 39, 889-907 (2014) · Zbl 1314.60066
[17] He, S.; Li, Z.; Zhang, S., Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program., 125, 353-383 (2010) · Zbl 1206.90124
[18] He, S.; Li, Z.; Zhang, S., Approximation algorithms for discrete polynomial optimization, J. Oper. Res. Soc. China, 1, 3-36 (2013) · Zbl 1281.90026
[19] Hillar, Cj; Lim, L-H, Most tensor problems are NP-hard, J. ACM, 60, 45 (2013) · Zbl 1281.68126
[20] Hou, K.; So, Am-C, Hardness and approximation results for \(L_p\)-ball constrained homogeneous polynomial optimization problems, Math. Oper. Res., 39, 1084-1108 (2014) · Zbl 1310.90091
[21] Hu, S., Relations of the nuclear norm of a tensor and its matrix flattenings, Linear Algebra Appl., 478, 188-199 (2015) · Zbl 1312.15027
[22] Jiang, B.; Ma, S.; Zhang, S., Tensor principal component analysis via convex optimization, Math. Program., 150, 423-457 (2015) · Zbl 1312.65008
[23] King, C., Inequalities for trace norms of \(2\times 2\) block matrices, Commun. Math. Phys., 242, 531-545 (2003) · Zbl 1049.15013
[24] King, C.; Nathanson, M., New trace norm inequalities for \(2\times 2\) blocks of diagonal matrices, Linear Algebra Appl., 389, 77-93 (2004) · Zbl 1064.15022
[25] Kolda, Tg; Bader, Bw, Tensor decompositions and applications, SIAM Rev., 51, 455-500 (2009) · Zbl 1173.65029
[26] Kong, X.; Meng, D., The bounds for the best rank-1 approximation ratio of a finite dimensional tensor space, Pac. J. Optim., 11, 323-337 (2015) · Zbl 1327.15055
[27] Kuczyński, J.; Woźniakowski, H., Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13, 1094-1122 (1992) · Zbl 0759.65016
[28] Kühn, T.; Peetre, J., Embedding constants of trilinear Schatten-von Neumann classes, Proc. Estonian Acad. Sci. Phys. Math., 55, 174-181 (2006) · Zbl 1125.46034
[29] Li, Z., Bounds on the spectral norm and the nuclear norm of a tensor based on tensor partitions, SIAM J. Matrix Anal. Appl., 37, 1440-1452 (2016) · Zbl 1348.15018
[30] Li, Z.; He, S.; Zhang, S., Approximation Methods for Polynomial Optimization: Models, Algorithms, and Applications (2012), New York: Springer, New York · Zbl 1298.90003
[31] Li, Z.; Nakatsukasa, Y.; Soma, T.; Uschmajew, A., On orthogonal tensors and best rank-one approximation ratio, SIAM J. Matrix Anal. Appl., 39, 400-425 (2018) · Zbl 1390.15081
[32] Lim, L.-H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing, vol. 1, pp. 129-132 (2005)
[33] Lim, L-H; Hogben, L., Tensors and hypermatrices, Handbook of Linear Algebra (2013), Boca Raton: CRC Press, Boca Raton
[34] Lim, L-H; Comon, P., Blind multilinear identification, IEEE Trans. Inf. Theory, 60, 1260-1280 (2014) · Zbl 1364.94139
[35] Magdon-Ismail, M.: A note on estimating the spectral norm of a matrix efficiently (2011). arXiv:1104.2076
[36] Mueller-Smith, C., Spasojević, P.: Column-wise symmetric block partitioned tensor decomposition. In: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 2956-2960 (2016)
[37] Nie, J.; Wang, L., Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Anal. Appl., 35, 1155-1179 (2014) · Zbl 1305.65134
[38] Nikiforov, V., Combinatorial methods for the spectral \(p\)-norm of hypermatrices, Linear Algebra Appl., 529, 324-354 (2017) · Zbl 1365.05183
[39] Phan, A.H., Cichocki, A.: Block decomposition for very large-scale nonnegative tensor factorization. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing, vol. 3, pp. 316-319 (2009)
[40] Qi, L., The best rank-one approximation ratio of a tensor space, SIAM J. Matrix Anal. Appl., 32, 430-442 (2011) · Zbl 1228.15010
[41] Ragnarsson, S.; Van Loan, Cf, Block tensor unfoldings, SIAM J. Matrix Anal. Appl., 33, 149-169 (2012) · Zbl 1246.15028
[42] Ragnarsson, S.; Van Loan, Cf, Block tensors and symmetric embeddings, Linear Algebra Appl., 438, 853-874 (2013) · Zbl 1390.15082
[43] Schur, I., Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlischen, J. Reine Angew. Math., 140, 1-28 (1911) · JFM 42.0367.01
[44] So, Am-C, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Math. Program., 192, 357-382 (2011) · Zbl 1230.90156
[45] Tonge, A., Equivalence constants for matrix norms: a problem of goldberg, Linear Algebra Appl., 306, 1-13 (2000) · Zbl 0956.15013
[46] Uschmajew, A.: Some results concerning rank-one truncated steepest descent directions in tensor spaces. In: Proceedings of the International Conference on Sampling Theory and Applications, pp. 415-419 (2015)
[47] Vannieuwenhoven, N.; Meerbergen, K.; Vandebril, R., Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking, SIAM J. Sci. Comput., 37, C415-C438 (2015) · Zbl 1320.65066
[48] Wang, M.; Dao Duc, K.; Fischer, J.; Song, Ys, Operator norm inequalities between tensor unfoldings on the partition lattice, Linear Algebra Appl., 520, 44-66 (2017) · Zbl 1359.15014
[49] Zhang, X.; Ling, C.; Qi, L., The best rank-1 approximation of a symmetric tensor and related spherical optimization problems, SIAM J. Matrix Anal. Appl., 33, 806-821 (2012) · Zbl 1269.15026
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.