Minimization problem involving matrix norm

8 次查看（过去 30 天）
Imam
Imam 2015-4-30
编辑： Matt J 2015-5-2
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
  2 个评论
Imam
Imam 2015-5-1
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2015-4-30
编辑：Matt J 2015-5-1
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.
  2 个评论
Imam
Imam 2015-5-1
编辑：Imam 2015-5-1
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
Matt J 2015-5-2
编辑：Matt J 2015-5-2
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))

请先登录，再进行评论。

更多回答（1 个）

Brendan Hamm
Brendan Hamm 2015-4-30
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.
  1 个评论
Matt J
Matt J 2015-4-30
编辑：Matt J 2015-4-30
The problem is convex, so any solution x will definitely be global.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by