A lower bound for the nearest correlation matrix problem based on the circulant mean
- PDF / 370,283 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 188 Views
A lower bound for the nearest correlation matrix problem based on the circulant mean M. V. Travaglia
Received: 5 October 2012 / Revised: 20 March 2013 / Accepted: 22 March 2013 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2013
Abstract This paper deals with the problem of finding the nearest correlation matrix to a given n × n symmetric matrix A. We say that X is a correlation matrix if it is symmetric positive semidefinite whose diagonal entries are equal to 1. The nearest correlation matrix to A is the one that minimizes its distance to A with relation to the Euclidean or Frobenius norm. The circulant mean of A, denoted by Ac , is the matrix obtained by averaging over the diagonals of A, with the diagonals being extended to the length n by a wrap-around. It turns out (due to a simple application of Jensen’s trace inequality) that the distance from Ac to its nearest correlation matrix will be a lower bound for the original distance. As the main result of this work, we compute the distance from Ac to its nearest correlation matrix by relating it to the eigenvalues of Ac . A motivation of the choice of the circulant mean is the following: we apply this lower bound and a related upper bound to the special case of the n × n Laplacian matrix with Dirichlet boundary conditions (a three-band Toeplitz matrix, which is not circulant, that is, is not equal to its circulant mean). In this application we show that the distance to its nearest correlation matrix behaves asymptotically as Cassymp n 1/2 with Cassymp ≈ 1.1165. Keywords Matrix nearness problem · Minimization problem involving matrices · Convex programming · Quadratic semidefinite programming · Circulant matrices · Laplacian matrices Mathematics Subject Classification (2000)
15A18 · 90C22
Communicated by Marcos Raydan. M. V. Travaglia (B) Departamento de Matemática, Centro de Ciências da Natureza, Universidade Federal do Piauí, Teresina , PI 64049-550, Brazil e-mail: [email protected]
123
M. V. Travaglia
1 Introduction We denote by Rn×n the set of the n × n real matrices and by S its subset of symmetric ones. We say that a matrix X ∈ S is positive semidefinite if its eigenvalues are nonnegative. We denote such subset of S as S+ . Let Se ⊂ Rn×n be the set of the matrices with all diagonal entries equal to 1. We are interested in the intersection set S+ ∩ Se , which is called the set of correlation matrices. This paper concerns itself with the following problem. For a given symmetric matrix A find the distance γ (A) := min{A − X : X ∈ S+ ∩ Se }
(1.1)
and the corresponding matrix X ∗ (A) ∈ S+ ∩ Se that attains this distance. In other words, γ (A) and X ∗ (A) are the minimum value and the minimizer of the minimization problem (1.1), respectively. The matrix X ∗ (A) is called the nearest correlation matrix to A. The norm n 2 in (1.1) is defined as C = i, j=1 Ci j . This norm is called Frobenius or Euclidean norm and comes from the inner product A, B := Tr{A T B}, where A, B ∈ Rn×n and Tr denotes the trace of matrix. It is
Data Loading...
