ebn0.net - Estimating a Complex Positive semi-definite Matrix using Noisy Observations of its Entries

$\newcommand{\re}{\operatorname{Re}}\newcommand{\im}{\operatorname{Im}}\newcommand{\vec}{\operatorname{vec}} \newcommand{\mat}{\operatorname{mat}}$ First some notation:

Use $\succeq 0$ to mean matrix positive semi-definiteness.
Use $\vec$ as the operation that reshapes an $n\times n$ matrix into a $n^2$ -vector by stacking its columns: $\vec := ([\mathbf{c} _1,\dots, \mathbf{c} _n] \mapsto \left[\begin{smallmatrix} \mathbf{c} _1 \\ \vdots \\ \mathbf{c} _n \end{smallmatrix} \right])$ , and write $\mat$ as the backwards operation.
For a square matrix $\mathbf{M}$ denote the $2\times 2$ minor corresponding to indices $(i,j)$ as $\mathbf{M} _{(i,j)} = \left[ \begin{smallmatrix} \mathbf{M} _{i,i} & \mathbf{M} _{i,j} \\ \mathbf{M} _{j,i} & \mathbf{M} _{j,j} \end{smallmatrix} \right]$ .

The setup:

$\mathbf{\Sigma}\in \mathbb{C}^{n\times n}$ is a covariance matrix we want to estimate.
$\mathbf{A}\in \mathbb{C}^{m\times n}$ is known and non-degenerate with $m\geq n$ .
$\mathbf{z} \in \mathbb{C}^m$ is a noise vector with zero mean and distribution $f _{\mathbf{z}}$
We observe $\mathbf{v} = \mathbf{A}(\vec \mathbf{\Sigma})+\mathbf{z}$

We will examine $\hat{\mathbf{s}}$ the "max-likelihood value for $\vec \mathbf{\Sigma}$ given $\mathbf{v}$ ":

$\begin{equation} \label{eqn:ml} \tag{1} \hat{\mathbf{s}} = \underset{\mathbf{s}\in \mathbb{C}^{n^2}: \mat \mathbf{s} \succeq 0}{\arg\max} f _{\mathbf{z}}(\mathbf{v}-\mathbf{A}\mathbf{s}). \end{equation}$

By Sylvester's criterion the constraint that $(\mat \mathbf{s}) \succeq 0$ is equivalent to the same constraint on each of $(\mat \mathbf{s})$ 's $2\times 2$ minors:

$\begin{align} \label{eqn:syl} \tag{2} \left\lbrace \mathbf{s}\in \mathbb{C}^{n^2}: \mat \mathbf{s}\succeq 0 \right\rbrace &= \bigcap _{i=1}^n \bigcap _{j=i+1}^n \left\lbrace \mathbf{s}\in \mathbb{C}^{n^2}: (\mat \mathbf{s}) _{(i,j)}\succeq 0 \right\rbrace. \end{align}$

Consider one of these constraint subsets. The eigenvalues $(u,v)$ for any $2\times 2$ complex Hermitian matrix $\mathbf{H} := \left[\begin{smallmatrix} a & b' \\ b & c\end{smallmatrix}\right]$ can be computed directly using trace and determinant rules:

$\begin{align} \label{eqn:uv} \tag{3} \left\lbrace \begin{matrix} u+v &=& a+c \hfill \\ \hfill uv &=& ac-|b|^2 \end{matrix}\right. \Leftrightarrow \left\lbrace \begin{matrix} u = \frac{1}{2} \left[\hphantom{-}\sqrt{(a-c)^2+4|b|^2} + (a+c) \right] \\ v = \frac{1}{2} \left[ -\sqrt{(a-c)^2+4|b|^2} + (a+c) \right] \end{matrix}\right. \end{align}$

And $\mathbf{H} \succeq 0$ iff $u,v \geq 0$ , viz. (considering $(\ref{eqn:uv})$ )

$\begin{equation} a,c, ac-|b|^2 \geq 0. \end{equation}$

Rewriting in explicit real-quadratic form,

$\begin{equation} \mathbf{H} \succeq 0 \text{ iff } a,\ c,\ [a,\re(b), \im(b), c] \mathbf{Q} \begin{bmatrix} a \\ \re(b) \\ \im(b) \\ c \end{bmatrix} \geq 0; \quad \mathbf{Q} := \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}. \end{equation}$

You can check that $\mathbf{Q}$ is negative semi-definite. As a result the set on the left of $(\ref{eqn:syl})$ comprises:

${n \choose 2}$ real negative semi-definite quadratic constraints from the $\mathbf{Q}$ matrices relating the diagonals and off-diagonals,
$n$ linear inequality constraints enforcing that the diagonals of $\mat \mathbf{s}$ be non-negative.

In total there are $n^2$ real variables involved:

The $n$ diagonal components of $\mat{\mathbf{s}}$ ,
The ${n \choose 2}$ components in the upper-triangular part of $\re(\mat{\mathbf{s}})$ ,
The ${n \choose 2}$ components in the upper-triangular part of $\im(\mat{\mathbf{s}})$ .

As long as the objective in $(\ref{eqn:ml}),\ (\mathbf{s}\mapsto f _{\mathbf{z}}(\mathbf{v}-\mathbf{A}\mathbf{s}))$ , considered as a function of the above $n^2$ real variables, is amenable to optimization then we can efficiently compute $\hat{\mathbf{s}}$ using, say, an interior-point method. This is the case, say, when $f _\mathbf{z}$ follows some positive-definite quadratic form on $\mathbb{C}^m$ .

$\frac{\boldsymbol{E_b}}{\boldsymbol{N_0}}$ .net

Estimating a Complex Positive semi-definite Matrix using Noisy Observations of its Entries

Comments