19 September 2017 in Mathematics of Computation
We establish several mathematical and computational properties of the nuclear norm for higher-order tensors. We show that like tensor rank, tensor nuclear norm is dependent on the choice of base field; the value of the nuclear norm of a real $3$-tensor depends on whether we regard it as a real $3$-tensor or a complex $3$-tensor with real entries. We show that every tensor has a nuclear norm attaining decomposition and every symmetric tensor has a symmetric nuclear norm attaining decomposition. There is a corresponding notion of nuclear rank that, unlike tensor rank, is lower semicontinuous. We establish an analogue of Banach’s theorem for tensor spectral norm and Comon’s conjecture for tensor rank; for a symmetric tensor, its symmetric nuclear norm always equals its nuclear norm. We show that computing tensor nuclear norm is NP-hard in several ways. Deciding weak membership in the nuclear norm unit ball of $3$-tensors is NP-hard, as is finding an $\varepsilon$-approximation of nuclear norm for $3$-tensors. In addition, the problem of computing spectral or nuclear norm of a $4$-tensor is NP-hard, even if we restrict the $4$-tensor to be bi-Hermitian, bisymmetric, positive semidefinite, nonnegative valued, or all of the above. We discuss some simple polynomial-time approximation bounds. As an aside, we show that computing the nuclear $(p,q)$-norm of a matrix is NP-hard in general but polynomial-time if $p=1$, $q = 1$, or $p=q=2$, with closed-form expressions for the nuclear $(1,q)$- and $(p,1)$-norms.
3 December 2013 in Physical Review Letters
Uncertainty relations are a distinctive characteristic of quantum theory that impose intrinsic limitations on the precision with which physical properties can be simultaneously determined. The modern work on uncertainty relations employs entropic measures to quantify the lack of knowledge associated with measuring noncommuting observables. However, there is no fundamental reason for using entropies as quantifiers; any functional relation that characterizes the uncertainty of the measurement outcomes defines an uncertainty relation. Starting from a very reasonable assumption of invariance under mere relabeling of the measurement outcomes, we show that Schur-concave functions are the most general uncertainty quantifiers. We then discover a fine-grained uncertainty relation that is given in terms of the majorization order between two probability vectors, significantly extending a majorization-based uncertainty relation first introduced in M. H. Partovi, Phys. Rev. A 84, 052117 (2011). Such a vector-type uncertainty relation generates an infinite family of distinct scalar uncertainty relations via the application of arbitrary uncertainty quantifiers. Our relation is therefore universal and captures the essence of uncertainty in quantum theory.
27 March 2014 in Foundations of Computational Mathematics
6 December 2012 in Frontiers of Mathematics in China
1 January 2008 in The Electronic Journal of Combinatorics
In this paper we study the maximum value of the largest eigenvalue for simple bipartite graphs, where the number of edges is given and the number of vertices on each side of the bipartition is given. We state a conjectured solution, which is an analog of the Brualdi-Hoffman conjecture for general graphs, and prove the conjecture in some special cases.
1 April 2011 in Journal of Mathematical Physics
We show that the linear group of automorphism of Hermitian matrices which preserves the set of separable states is generated by natural automorphisms: change of an orthonormal basis in each tensor factor, partial transpose in each tensor factor, and interchanging two tensor factors of the same dimension. We apply our results to the preservers of the product numerical range.