Minimization problem involving matrix norm

I have a matrix A of size n x n. This matrix is represented as a linear combination of m basis matrices with expansion coefficients denoted by a vector x of size 1 x m as it should be. I want to minimize this equations:

minimize norm(FBx - R), subject to x >= 0.

the expression FBx is not to be understood as a matrix multiplication, instead it represents operators action. B is the operator corresponding to the basis matrices, so Bx means the expansion of A into the basis matrices, one can also understand Bx as the matrix A itself. F is the 2D Fourier operator, so FBx is the the 2D FFT of A. R is a given matrix with size n x n.

My question is what type of minimzation function I can use in MATLAB? The above problem doesn't seem to be a linear programming type, so I was wondering if there is MATLAB function which I can readily use for this purpose. By the way I'm new in optimization problem.

EDIT: the output is x

[Matt J]

Is this the Frobenius norm?

[Imam]

Actually the problem doesn't seem to specify the type of the norm, but if you think the Frobenius norm is the easiest (I'm not sure) you can assume so.

Answer 1

[Matt J]

I'm assuming the norm in question is the Frobenius norm. When appropriately scaled, the 2D FFT is an orthogonal operator. The problem can then be rewritten

    minimize norm(Bx - FtR), subject to x >= 0

where FtR is the 2D orthonormalized inverse FFT of R.

From that point onward, the NxN shape of the original matrices becomes irrelevant. You can rewrite the problem in terms of basis vectors instead of basis matrices. Specifically, you can write the operator B in explicit matrix form just by reshaping your basis matrices B_i into column vectors and making those the columns of an N^2 x M matrix where M is the number of basis matrices,

    B=[B_1(:),  B_2(:),...B_M(:)];

You would reshape FtR similarly. The minimization problem can then be solved in a straightforward manner either with lsqlin or lsqnonneg.

[Imam]

Actually this whole time I'm having a hard time thinking of if there is any possible way to write the operator B into a single matrix. Up to now I only know the 1D case: expanding a vector into some basis vectors, not the 2D case where I have to expand a matrix into basis matrices. So would you please elaborate more how I can transform B_i from a matrix to a vector of length N^2? Do I simply stack its columns on top of another, if so is there a rule of how I should put the order?

Since now the problem has the form of a vector, the question of whether to use Frobenius norm is irrelevant. So the next step would be deciding which vector norm I should use, if in the original problem it was Frobenius norm, does this mean in the vector form I must use the l_2 norm?

And btw what is a 2D orthonormalized FFT? Is it the usual FFT but divided by 1/sqrt(N) in addition?

[Matt J]

So would you please elaborate more how I can transform B_i from a matrix to a vector of length N^2?

That was in my original answer. The command B_i(:) will stack the columns of B_i into a vector. If you currently have the basis matrices in the form of an NxNxM stack you could also just use the reshape command

    B=reshape(basisStack,N^2,M);

Since now the problem has the form of a vector, the question of whether to use Frobenius norm is irrelevant.

No, it's not irrelevant. If, for example, the norm is the usual l_2 induced matrix norm then the value of the objective function is obtained by computing the maximum eigenvalue of the error matrix, Bx - FtR. Thus, the NxN matrix shape now matters again.

So the next step would be deciding which vector norm I should use, if in the original problem it was Frobenius norm, does this mean in the vector form I must use the l_2 norm?

Yes, that's what simplifies everything. Because we have

    norm(A,'fro')=norm(A(:),2)

Do I simply stack its columns on top of another, if so is there a rule of how I should put the order?

The order shouldn't matter because the value of Frobenius and vector l2-norm doesn't depend on the order of the elements. Easiest just to stack the columns, however.

And btw what is a 2D orthonormalized FFT? Is it the usual FFT but divided by 1/sqrt(N) in addition?

For 1D vectors, yes. More generally, for MATLAB's higher dimensional FFTs, you normalize as

   fftn(X)/sqrt(numel(X))

   ifftn(X)*sqrt(numel(X))

Answer 2

[Brendan Hamm]

The 2-norm by itself is a non-linear operation, so you will want to use fmincon. Really any matrix norm will be non-linear, so this will likely work for you. I should note that there is no guarantee that the returned minimum is a global minimum (especially when you have such a large feasible region (only bound is x>=0). For this reason you might want to take a look at multistart in the Global Optimization toolbox.

[Matt J]

The problem is convex, so any solution x will definitely be global.