## 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}$":

$$\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}).$$

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})$)

$$a,c, ac-|b|^2 \geq 0.$$

$$\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}.$$

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$.