trying to find a linear combination of matrixes in order to minimize the error between the linear combination and a target matrix
8 views (last 30 days)
Show older comments
Hi everyone, i'm trying to find a solution to my problem, i need to calculate coefficient for a linear combination of matrix in order to minimize the difference between a target matrix and my linear combination.
in symbols : Error = TargetMatrix - (aA+bB+cC+dD+eE+fF+gG+hH+iI+jJ+kK+lL);
I need to find a, b, c , d ,e , f ,g, h , i ,j ,k and l in order to obtain the minimum Error;
1 Comment
Jon
on 27 Jul 2023
To minimize something you must say how you are measuring how big it is. In your case you are trying to minimize, a matrix, so you must say, what norm you are using to measure how "big" the matrix is. See https://www.mathworks.com/help/matlab/ref/norm.html
Accepted Answer
John D'Errico
on 27 Jul 2023
Edited: John D'Errico
on 27 Jul 2023
Trivially easy. What you need to do it to convert the problem to a set of VECTORS. Unroll the matrices into vectors. Then make one large matrix. Next, you need to learn to use matrices in general. DON'T have 9 different matrices. Have ONE three dimensional matrix. LEARN TO USE MATLAB AS IT IS DESiGNED TO BE USED.
matrices = rand(4,4,9);
Lacking any data, I have created 9 random matrices, each 4x4.
M = reshape(matrices,[4*4,9]);
I'll choose an array of all ones as the goal matrix, so we can see how well we did.
Target = ones(4,4);
Treshape = Target(:);
Now I have ONE matrix, of size 16x9. Here, each of the original matrices is one column of M. The right hand side for the problem is just the target matrix, also reshaped into a vector of length 16,
At this point, the problem is just one of a simple multiple linear regression.
coeffs = M\Treshape
How well did we do?
pred = reshape(M*coeffs,[4,4])
Not too bad, actually, since the target was all ones.
Again, learn to use MATLAB, as it was designed to be used.
5 Comments
Jon
on 28 Jul 2023
Wow, thank you so much for your insights on that! Good to know that for the other norms there are linear programming solutions. I was already starting to see that solving this with fminunc was getting a little fiddly for larger collections of matrices. Woud be much better to have a dependable linear programming solution. Regarding the choice of norm, I'm wondering if there is some notion that if we make one norm "very" small we also make the others small, so for most practical purposes it doesn't really matter what norm we choose. Maybe the choice of norm really only comes in to play for situations where some constraints keep the minimal norm relatively large, so the differences between norms become more apparent. Anyhow, I guess this discussion is probably going well beyond what was asked by the OP, but it is interesting, at least to me :)
Bruno Luong
on 28 Jul 2023
Edited: Bruno Luong
on 28 Jul 2023
@John D'Errico " I can probably write the 1-norm case from memory, and I'm pretty sure the inf-norm has a solution via linprog too, but it has been 40 years since I learned the trick.)"
For matrix actually the Inf-norm is the 1-norm of its transpose.
A=rand(4)
norm(A,Inf)
norm(A.',1)
You probably have in mind vector where 1-norm and Inf-norm are fundamentally different.
Never minimize 1-norm or Inf-norm for matrix myself, but yes it should be doable with linprog as they are "flat" norm, and I wonder if problem-based solver can be smart enough to figure it out.
More Answers (1)
Jon
on 27 Jul 2023
Edited: Jon
on 27 Jul 2023
Here's a much more elaborate approach that can be modified to use a specific choice of matrix norm to be minimized. I would use @John D'Errico's very clean and simple approach unless there were some overwhelming reason that the choice of matrix norm was very important. I am including this just in case it is of interest, and also to get @John D'Errico perspective on whether there are ever any cases where some other matrix norm might be needed. I also not that this approach requires the Optimization toolbox. Also using fminunc here seems to have some potential issues when the number of matrices to be regressed gets large (e.g. 10).
% Find linear combination of matrices to approximate a target matrix
% min(||A - a1*B1+a2*B2+ ...anBn||) where a1,a2,.. are scalars, A, B1, B2,...
% are mRow by nCol matrices and || || is a matrix norm
% in this case we will use the p=2 norm for || ||, but you could edit this
% to use the norm of your choosing
% Make some example data using random matrices, you would use the matrices
% of interest for your problem
mRow = 3;
nCol = 3;
n = 7; % number of matrices to be included in fit
% create an example where we know the exact answer
B = randn(mRow,nCol,n);
bExact = randn(n,1);
Aexact = lincomb(B,bExact);
% Create target matrix that can't be exactly acheived as linear combination
A = Aexact + 100*eps*randn(mRow,nCol);
% Find optimal solution, you should check exit flag, for this example I
% skipped this for the example
[bOpt,exitflag] = bestLinComb(A,B)
% Compare optimal b and bExact
deltab = bOpt - bExact
% Compare approximated A and target
Aopt = lincomb(B,bOpt);
delta = A - Aopt
% Compare to very simple approach
bAlt = reshape(B,mRow*nCol,n)\A(:)
%
function [b,exitflag] = bestLinComb(A,B)
% A - target matrix
% B - m by n by p array of matrices to be combined
b0 = zeros(size(B,3),1);
options = optimoptions('fminunc','Display','iter-detailed',...
'MaxFunctionEvaluations',1e6);
[b,~,exitflag] = fminunc(@errnorm,b0,options);
% function to find best linear combination of matrices
function e = errnorm(b)
% error whose norm is to be minimized
% you could use a different norm here, e,g, 1, inf,"fro"
e = norm(A - lincomb(B,b),2); % minimize svd
end
end
function B = lincomb(A,a)
% calculates linear combination of matrices
% A is a m by n by p array of matrices
% a is a length p vector
% B = a(1)*A(:,:,1) + a(2)*A(:,:,2) + ... a(p)*A(:,:,p)
% compute linear combination, we first turn each matrix into a vector
% columnwise, form a matrix from these vectors and then use ordinary matrix
% multiplication, and finally reshape to the original size
[m,n,p] = size(A);
B = reshape(reshape(A,m*n,p)*a(:),m,n);
end
0 Comments
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!