Solving a matrix norm minimization problem with unknown scalar AND vector/matrix

1

Being a newbie to optimization I stumbled upon a problem formulation I don’t seem to be able to put into a form I can use with one of the proposed algorithms in cvx (btw, thanks to the responsible people for the work they put into this project).

Let me jump right to it. The model I have is:

C = AXA^\text{H}+\sigma^2 I,

with C=pp^\text{H} being a M\times M complex matrix consisting of the product of a M\times 1 vector of known values with itself (i.e. its Hermitian transpose).
The complex M\times N matrix A is also known, I is the M\times M identity matrix.
What I need is the best fit for X and \sigma, where \sigma is a scalar (kind of an error/noise parameter), and X is a N\times N diagonal matrix.

The minimization is formulated as follows:

\begin{array}{ll} \text{minimize}&||C - AXA^\text{H} - \sigma^2 I||_\text{F}^2 \\ \text{subject to} &X_{nn} \geq 0,~n=1,... ,N\\ &\textstyle\sum_{n=1}^N X_{nn} \leq \lambda\\ &X ~\text{diagonal} \\ &\sigma^2\geq 0. \end{array}

The parameter \lambda is additional constraint for the sum of the diagonal elements of X can be chosen more or less arbitrarily.

From looking at it this problem doesn’t seem very complicated to me, but up to now I didn’t find any practicable formulation that can be put into a python or matlab program.

Any hints or help how to approach this with cvx would be greatly appreciated. If something is unclear just let me know :slight_smile:

Thanks in advance,

Jo

2

Frankly this is a relatively simple problem for CVX to handle. I will be curious to hear why the user manual, example library, etc. were not sufficient to show you how this could be specified. But I am grateful for the first outside question to come into this forum! So I am happy to answer.

There are a couple of tricks that I think are worth mentioning here.

  • Use a variable sigma_sq to represent \\sigma^2. If instead you declare a variable sigma to represent \\sigma, the problem will not be convex. This does mean, however, that you must explicitly constrain sigma_sq to be nonnegative.
  • There’s no need to square the norm in the objective; the problem is equivalent without it. In fact, with the solvers CVX uses it is better if you do not use a quadratic.
  • There are two ways you can declare X: you can declare it as a diagonal matrix, or you can declare it as a vector. I’ll show you both.

So here we are: declaring x as a vector,

cvx_begin
    variables sigma_sq x(n)
    minimize(norm(C-A*diag(x)*A'-sigma_sq*eye(n),'Fro'))
    subject to
        x >= 0
        sum(x) <= lambda
        sigma_sq >= 0
cvx_end

Alternatively, declaring X as a matrix with diagonal structure…

cvx_begin
    variable sigma_sq 
    variable X(n,n) diagonal
    minimize(norm(C-A*X*A'-sigma_sq*eye(n),'Fro'))
    subject to
        diag(X) >= 0
        trace(X) <= lambda
        sigma_sq >= 0
cvx_end
3

Please note that I have changed the title of your post. Your problem is not a linear minimization problem. So if someone was searching for help with norm minimization, they would not find your post! (Of course, since yours is the first, that won’t be a problem now… but later…)