How to solve a special linear equation Ax=b? A is a row vector.
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Benson Gou
el 3 de Jul. de 2019
Comentada: Benson Gou
el 19 de Jul. de 2019
Dear All,
I am trying to solve the following linear equation Ax=b:
[a1 a2 ... an][x1 x2 ... xn]' = b. where b is a complex number, a_i is also complex, and x_i is 1 or 0. This equation is unsolvable because the number of variables is n while the equation is 1. But if we add another condition: x is the sparse solution (number of nonzero entries is known) , there exists a unique solution.
For example, [0.1+0.2i 0.2+0.3i 0.4+0.5i 0.6+7i 0.8+0.9i]*[x1 x2 x3 x4 x5 x6 x7 x8 x9]' = 0.5+0.7i. If we know there are 2 non-zeros in x, then we got a unique solution x1=x3=1, others are zero.
But would someone tell me how to solve this equation using Matlab code?
Thanks a lot.
Benson
1 comentario
Steven Lord
el 3 de Jul. de 2019
How large a value of n do you plan to use?
And no, the solution under the one condition that x is as sparse as possible does not guarantee a unique solution in general unless a must contain unique values. Let a = [1 1] and b = 1. Both x = [1 0] and x = [0 1] are solutions and both have only one nonzero element.
In fact, even uniqueness of values in a plus a sparsity restriction on x does not guarantee a unique solution. Let a = [1 2 3 4] and b = 5. Both [1 0 0 1] and [0 1 1 0] satisfy the problem and both have only two nonzero elements. None of the elements in a is greater than or equal to b, so any solution must have at least two nonzero elements.
So this problem, as described, seems to fall under the second of Cleve's Golden Rules of computation. Are there other requirements on a, b, and/or x you're not telling us that might make the solution unique?
Respuesta aceptada
Bruno Luong
el 3 de Jul. de 2019
Editada: Bruno Luong
el 3 de Jul. de 2019
If you have optimization toolbox
A=[0.1+0.2i 0.2+0.3i 0.4+0.5i 0.6+7i 0.8+0.9i]
b = 0.5+0.7i;
nz = 2;
AA = [real(A); imag(A)]*10;
bb = [real(b); imag(b)]*10;
AA(end+1,:) = 1;
bb(end+1) = nz;
n = size(AA,2);
fdummy = ones(n,1);
lb = zeros(n,1);
ub = ones(n,1);
x = intlinprog(fdummy,1:n,[],[],AA,bb,lb,ub)
Solution returned is:
x =
1
0
1
0
0
If there are more than 1 solution, they can be obtained by changing fdummy.
8 comentarios
Bruno Luong
el 18 de Jul. de 2019
Editada: Bruno Luong
el 18 de Jul. de 2019
I suggest you to try formuate with the case p=Inf, it's not difficult when you write down the equation.
Edit: p=1 more difficult than p=Inf, and not as I wrong stated previously
Más respuestas (1)
Bruno Luong
el 18 de Jul. de 2019
Editada: Bruno Luong
el 18 de Jul. de 2019
Code for p = Inf and noise_threshold = 0.01;
A = [0.103+0.201i 0.196+0.294i 0.401+0.499i 0.602+6.993i 0.803+0.892i]
b = 0.5+0.7i;
noise_threshold = 0.01;
AA = [+real(A);
+imag(A);
-real(A);
-imag(A)];
bb = [+real(b);
+imag(b);
-real(b);
-imag(b)] + noise_threshold;
n = size(AA,2);
fdummy = ones(n,1);
lb = zeros(n,1);
ub = ones(n,1);
x = intlinprog(fdummy,1:n,AA,bb,[],[],lb,ub)
if isempty(x)
fprintf('noise_threshold = %f too small', noise_threshold);
end
% Check the "fit" result
A*x
b
Ver también
Categorías
Más información sobre Sparse Matrices en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!