research-article

Bounds on the Spectral Norm and the Nuclear Norm of a Tensor Based on Tensor Partitions

Author:

Zhening LiAuthors Info & Claims

SIAM Journal on Matrix Analysis and Applications, Volume 37, Issue 4

Pages 1440 - 1452

https://doi.org/10.1137/15M1028777

Published: 01 January 2016 Publication History

Abstract

It is known that computing the spectral norm and the nuclear norm of a tensor is NP-hard in general. In this paper, we provide neat bounds for the spectral norm and the nuclear norm of a tensor based on tensor partitions. The spectral norm (respectively, the nuclear norm) can be lower and upper bounded by manipulating the spectral norms (respectively, the nuclear norms) of its subtensors. The bounds are sharp in general. When a tensor is partitioned into its matrix slices, our inequalities provide polynomial-time worst-case approximation bounds for computing the spectral norm and the nuclear norm of the tensor.

References

[1]

L. De Lathauwer, B. De Moor, and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253--1278.

[2]

H. Derksen, On the nuclear norm and the singular value decomposition of tensors, Found. Comput. Math., 16 (2016), pp. 779--811.

[3]

S. Friedland and L.-H. Lim, Nuclear Norm of Higher-Order Tensors, preprint, arXiv:1410.6072, 2016.

[4]

S. Gandy, B. Recht, and I. Yamada, Tensor completion and low-$n$-rank tensor recovery via convex optimization, Inverse Problems, 27 (2011), 025010.

[5]

G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1996.

[6]

S. He, B. Jiang, Z. Li, and S. Zhang, Probability bounds for polynomial functions in random variables, Math. Oper. Res., 39 (2014), pp. 889--907.

[7]

S. He, Z. Li, and S. Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program., 125 (2010), pp. 353--383.

[8]

N. J. Higham, Estimating the matrix $p$-norm, Numer. Math., 62 (1992), pp. 539--555.

[9]

C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard, J. ACM, 60 (2013), 45.

[10]

R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985.

[11]

S. Hu, Relations of the nuclear norm of a tensor and its matrix flattenings, Linear Algebra Appl., 478 (2015), pp. 188--199.

[12]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), pp. 455--500.

[13]

Z. Li, S. He, and S. Zhang, Approximation Methods for Polynomial Optimization: Models, Algorithms, and Applications, Springer, New York, 2012.

[14]

L.-H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, IEEE, New York, 2005, pp. 129--132.

[15]

L.-H. Lim, Tensors and hypermatrices, in Handbook of Linear Algebra, Chapter 15, 2nd ed., L. Hogben, ed., CRC Press, Boca Raton, FL, 2013.

[16]

L.-H. Lim and P. Comon, Blind multilinear identification, IEEE Trans. Inform. Theory, 60 (2014), pp. 1260--1280.

[17]

J. Liu, P. Musialski, P. Wonka, and J. Ye, Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), pp. 208--220.

[18]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), pp. 1302--1324.

[19]

S. Ragnarsson and C. F. Van Loan, Block tensors and symmetric embeddings, Linear Algebra Appl., 438 (2013), pp. 853--874.

[20]

A. M.-C. So, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Math. Program., 192 (2011), pp. 357--382.

Cited By

Zeng C(2024)On the tensor spectral -norm and its higher order power methodCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-024-00588-y61:3Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1007/s10092-024-00588-y
Zeng C(2023)Further results on tensor nuclear normsCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-023-00528-260:3Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1007/s10092-023-00528-2

Recommendations

On norm compression inequalities for partitioned block tensors
Abstract
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 ... $(^{})$
On the tensor spectral $p$ -norm and its higher order power method
Abstract
Tensor spectral $p$ -norms are generalizations of matrix induced norms. Matrix induced norms are an important type of matrix norms, and tensor spectral $p$ -norms are also important in applications. We discuss some basic properties of tensor spectral $p$ -...
Nonlocal image denoising via adaptive tensor nuclear norm minimization

Nonlocal self-similarity shows great potential in image denoising. Therefore, the denoising performance can be attained by accurately exploiting the nonlocal prior. In this paper, we model nonlocal similar patches through the multi-linear approach and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Matrix Analysis and Applications

SIAM Journal on Matrix Analysis and Applications Volume 37, Issue 4

2016

407 pages

ISSN:0895-4798

DOI:10.1137/sjmael.37.4

Issue’s Table of Contents

© 2016, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2016

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zeng C(2024)On the tensor spectral -norm and its higher order power methodCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-024-00588-y61:3Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1007/s10092-024-00588-y
Zeng C(2023)Further results on tensor nuclear normsCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-023-00528-260:3Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1007/s10092-023-00528-2

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents