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

Bo Jiang, Simai He, Zhening Li, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

91 Downloads (Pure)

Abstract

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 (xTQx)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 2n4+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.
Original languageEnglish
Pages (from-to)775-788
JournalMathematics of Operations Research
Volume39
Issue number3
Early online date30 Oct 2013
DOIs
Publication statusPublished - Aug 2014

Keywords

  • cone of moments
  • uncorrelated random variables
  • Hilbert's identity
  • matrix norm

Fingerprint

Dive into the research topics of 'Moments tensors, Hilbert's identity, and k-wise uncorrelated random variables'. Together they form a unique fingerprint.

Cite this