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:

The setup:

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:

In total there are n^2 real variables involved:

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.