2
$\begingroup$

Given matrices $A, B \in \mathbb{C}^{(n-s) \times n}$ and matrix $\Sigma \in \mathbb{C}^{n \times n}$, I want to solve the following equality-constrained minimization problem

$$\begin{array}{ll} \underset{X \in \mathbb{C}^{n \times n}}{\text{minimize}} & \| \Sigma - X \cdot X^H \|_F\\ \text{subject to} & A X = B\end{array}$$

where $X^H = X^*$ is the hermitian conjugate (transpose and complex conjugate) and $\| \cdot \|_F$ is the Frobenius norm.

First we note that $\| Y \|_F^2 = \operatorname{tr}(YY^H)$ so minimizing $$ \operatorname{trace}\left( \Sigma\Sigma^H - \Sigma X X^H - X X^H \Sigma^H + X X^H X X^H \right) $$ is equivalent to minimizing the original expression.

First I try to see if there is an analytic solution (closed expression) to this constrained optimization problem, and the natural thing to do is try Lagrange Multipliers Method: $$ f(X) = \operatorname{trace}( (\Sigma - XX^H)(\Sigma - XX^H)^H ) + \lambda (A X - B) $$ but then I encountered two problem:

  1. What is $\lambda$? It can't be a scalar because the second term is a matrix and the first is a scalar. Moreover, there is no matrix that gives a scalar by pre- or post-multiply the second term (the constrain). A possible solution is to write each of the $(n-s) \times n$ equations separately and assign to each a different $\lambda_{i,j}$ with $i=1,...,n-s$ and $j=1,...,n$ and sum them (this will give us $(n-s)n$ terms in $f(X)$). Another solution is to replace this terms with $\langle \lambda , AX - B \rangle$ when $\lambda \in \mathbb{C}^{(n-s)\times n}$.
  2. Since there are expressions of the form $X X^H$ which include $z \cdot \bar{z}$ the first term is not differentiable in the complex sense. This hampers Lagrange Multipliers and other gradient based algorithms.

See How to set up Lagrangian optimization with matrix constrains for discussion of question 1.

Am I wrong here? Or these two arguments indeed show that obtaining analytic expression via Largrange Multipliers is not feasible?

Another idea is to try use the (Moore-Penrose) pseudo-inverse of $A$ to write $X = A^+ B$ but this over-determines $X$ which couldn't be the right solution (since if determined uniquely by the constrain then there is no minimization problem). Note that since $B \in \mathbb{C}^{(n-s) \times n}$ there are more variables ($X_{i,j}$) than equations, so there are $n^2 - (n-s) \times n = sn$ degrees of freedom in $X$.

If there is no analytic solution, what is the algorithmic way to solve this constrained minimization problem? I want to be able to program it and check it with Python using packages such as NumPy and SciPy. (Remark: algorithms that use real gradients probably won't work here because of the term $XX^H$ which is not differentiable in the complex sense.) Numerical optimization algorithms will be fine too.

Related questions:

General resources on complex optimization:

$\endgroup$
3
  • $\begingroup$ The TensorLab manual ( tensorlab.net/doc/complexoptimization.html ) offers ways to handle complex optimization using cogradients $\frac{\partial f}{\partial z}$ and $\frac{\partial f}{\partial \bar{z}}$. The question if there is an optimization function in Python that supports using these complex cogradients. $\endgroup$ Commented Jun 1, 2020 at 14:20
  • $\begingroup$ Thanks, I carried over the real operator from the scalar product $\langle A , B \rangle = \operatorname{Re}(\operatorname{trace}(A^H B))$ of (2.1) in hal.inria.fr/hal-01422932v2/document . Since norm is always real, this Re is redundant. I edited the questions accordingly. This is the first time I encounter complex optimization and therefore I am not so fluent in setting and underlying notions. $\endgroup$ Commented Jun 1, 2020 at 15:39
  • 1
    $\begingroup$ The Lagrange multiplier is a matrix. Take a look at this. Also, take a look at the Frobenius inner product. $\endgroup$ Commented Jun 1, 2020 at 15:41

1 Answer 1

1
$\begingroup$

I am not a big fan of Lagrangian relaxation. I have never found it generic enough. I would rather go with a linear fusion approach.

Let's introduce more matrices to be able to express a more powerful problem.

$X_h$ approximate $X^H$

$X_i$ approximate $X^{-1}$ if exists, or some well behaved $X^{\dagger}$ pseudoinverse if it doesn't.

Now we can write $$\|X_i\Sigma - X_h\|_F$$

And regularization terms $\alpha\|AX-B\|$, $\beta\|X_i X - I\|$, $\gamma\|T X_h - X\|$

Where T does conjugate transpose on vectorisation.

Now there remains one un-linearity here : The $\beta$ term.

So a linear least squares will not be enough.

But we can do an iterated two-stage linear-least squares.

  1. First phase optimizes $X,X_h$,
  2. Second phase optimizes $X_i$

Using Kronecker products we can express "T" operation above with a matrix on the vectorization of $X_h$.

The linear fusion comes into play when we connect $X$ and $X_h$ through $\gamma$-regularization and $X$ and $X_i$ through $\beta$-regularization

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I have two questions: (1) What is the linear fusion methos and how it is done? Reference will also be good. (2) In "iterated two-stage" do you mean that I repeat phases 1 and 2 several time (typically how many times?) until $X$, $X_h$ and $X_i$ converge? $\endgroup$ Commented Jun 2, 2020 at 8:37
  • $\begingroup$ @Triceratops You can sadly not read about linear fusion anywhere yet, because the inventor hasn't written a book about it yet. For the purpose of applying it to this question the Wikipedia page on "Kronecker product"s should suffice. Yes iteratively solving and updating linear least squares systems until they converge. $\endgroup$ Commented Jun 2, 2020 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .