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
采纳的回答
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 个评论
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
2015-4-30
0 个投票
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 个评论
类别
在 帮助中心 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息
Translated by 
