TY - JOUR

T1 - Moments tensors, Hilbert's identity, and k-wise uncorrelated random variables

AU - Jiang, Bo

AU - He, Simai

AU - Li, Zhening

AU - Zhang, Shuzhong

PY - 2014/8

Y1 - 2014/8

N2 - In this paper, we introduce a notion to be called k-wise uncorrelated random variables, which is similar but not identical to the so-called k-wise independent random variables in the literature. We show how to construct k-wise uncorrelated random variables by a simple procedure. The constructed random variables can be applied, e.g., to express the quartic polynomial (x TQx)2, where Q is an n×n positive semidefinite matrix, by a sum of fourth powered polynomial terms, known as Hilbert's identity. By virtue of the proposed construction, the number of required terms is no more than 2n 4 + n. This implies that it is possible to find a (2n4 + n)-point distribution whose fourth moments tensor is exactly the symmetrization of Q ⊗ Q. Moreover, we prove that the number of required fourth powered polynomial terms to express (xTQx)2 is at least n(n+1)=2. The result is applied to prove that computing the matrix 2 → 4 norm is NP-hard. Extensions of the results to complex random variables are discussed as well.

AB - In this paper, we introduce a notion to be called k-wise uncorrelated random variables, which is similar but not identical to the so-called k-wise independent random variables in the literature. We show how to construct k-wise uncorrelated random variables by a simple procedure. The constructed random variables can be applied, e.g., to express the quartic polynomial (x TQx)2, where Q is an n×n positive semidefinite matrix, by a sum of fourth powered polynomial terms, known as Hilbert's identity. By virtue of the proposed construction, the number of required terms is no more than 2n 4 + n. This implies that it is possible to find a (2n4 + n)-point distribution whose fourth moments tensor is exactly the symmetrization of Q ⊗ Q. Moreover, we prove that the number of required fourth powered polynomial terms to express (xTQx)2 is at least n(n+1)=2. The result is applied to prove that computing the matrix 2 → 4 norm is NP-hard. Extensions of the results to complex random variables are discussed as well.

KW - Cone of moments

KW - Hilbert's identity

KW - Matrix norm

KW - Uncorrelated random variables

UR - http://www.scopus.com/inward/record.url?scp=84906688159&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906688159&partnerID=8YFLogxK

U2 - 10.1287/moor.2013.0626

DO - 10.1287/moor.2013.0626

M3 - Article

AN - SCOPUS:84906688159

SN - 0364-765X

VL - 39

SP - 775

EP - 788

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 3

ER -