Loading...
Please wait, while we are loading the content...
Integer representation of a positive-definite matrix
| Content Provider | Semantic Scholar |
|---|---|
| Author | Tropp, Joel A. |
| Copyright Year | 2015 |
| Abstract | This note establishes that every positive-definite matrix can be written as a positive linear combination of outer products of integer-valued vectors whose entries are bounded by the geometric mean of the condition number and the dimension of the matrix. 1. MOTIVATION This note addresses a geometric question that arises in the theory of discrete normal approximation [BLX15]. The problem requires us to represent a nonsingular covariance matrix as a positive linear combination of outer products of integer vectors. The challenge is to obtain an optimal bound on the magnitude of the integers required as a function of the condition number of the matrix. We establish the following result. Theorem 1.1. For positive integers m and d, define a set of bounded integer vectors: Zm := { z ∈Zd : |zi | ≤ m for i = 1, . . . ,d } . Let A be a real d ×d positive-definite matrix with (finite) spectral condition number κ(A) :=λmax(A)/λmin(A), where λmax and λmin denote the maximum and minimum eigenvalue maps. Every such matrix A can be expressed as A= r ∑ i=1 αiziz ∗ i where zi ∈Zm and m ≤ 1+ 1 2 √ (d −1) ·κ(A). The coefficients αi are positive, and the number r of terms satisfies r ≤ d(d +1)/2−1. The symbol ∗ refers to the transpose operation. This result has an alternative interpretation via matrix factorization: A=Z∆Z∗. In this expression, Z is a d × r integer matrix with entries bounded by m. The r × r matrix ∆ is nonnegative and diagonal. The proof of Theorem 1.1 appears in Section 3. Section 4 demonstrates that the dependence on the condition number cannot be improved. We believe that the dependence on the dimension is also optimal, but we were not find an example that supports this point. 2. NOTATION & BACKGROUND This section contains brief preliminaries. The books [HJ90, Bha97, Bar02, BV04] are good foundational references for the techniques in this paper. We use lowercase italic letters, such as c, for scalars. Lowercase boldface letters, such as z, denote vectors. Uppercase boldface letters, such as A, refer to matrices. We write zi for the i th component of a vector z, and ai j for the (i , j ) component of a matrix A. The j th column of the matrix A will be denoted by a j . We work primarily in the real linear spaceHd of real d ×d symmetric matrices, equipped with the usual componentwise addition and scalar multiplication: H := {A ∈Rd×d :A=A∗}. Date: 26 May 2015. Revised: 31 May 2015. 2010 Mathematics Subject Classification. Primary: 52A99. Secondary: 52C99. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www2.ims.nus.edu.sg/preprints/2015-17.pdf |
| Alternate Webpage(s) | http://ims.nus.edu.sg/preprints/2015-17.pdf |
| Alternate Webpage(s) | http://www2.ims.nus.edu.sg/preprints/ab2015-17.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
