How to solve a special linear equation Ax=b? A is a row vector.

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

[Steven Lord]

This sounds somewhat like the knapsack problem or the change-making problem.

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?

Answer 1

[Bruno Luong]

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.

[Benson Gou]

Hi, Bruno,

Thanks for your great help. For the same question, but how about if we do not know the # of non-zeros in x? How can I obtain the sparse solution of x for a given A and b?

Thanks.

Bei

[Bruno Luong]

I believe you simply have to delete the last constraint in my code

AA(end+1,:) = 1;
bb(end+1) = nz;

[Benson Gou]

Dear Bruno,

Thanks a lot for your great help!

Benson

[Benson Gou]

Hi, Bruno,

For actual cases, entries in A are contaminated by noise. For the original example, I added noise to all elements in A, and then I could not get the correct answers of x using intlinprog. Do you have any ideas to handle this situation?

Thanks a lot.

Benson

[Bruno Luong]

Instead of imposing equality

A*x = b

you can relax to inequality constraints

norm(A*x - b, p) <= noise_threshold

When chosen p as 1 or Inf (flat-norm) the pb can still be formullated as LP.

[Benson Gou]

Dear Bruno,

Thanks a lot for your prompt reply. But would you please show for the following problem how to implement intlinprog using "norm(A*x - b, p) <= noise_threshold"?

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;

A is contaminated by noise.

Thanks a lot again.

Benson

[Bruno Luong]

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

[Benson Gou]

I tried for p=1 case. I relaxed the absolute value of ||A*x-b||_1<=epthon by two inequalities: A*x-b<=epthon and -A*x+b<=epthon. Combined these two inequailties into one inequality and I got A1*x-b1<=epthon1. Then I applied intlinprog on this inequality, but I got nun x. I checked the error message and knew that intlinprog stopped running before reaching a solution. I do not know why. Thanks a lot again for your great help. -Benson

Answer 2

[Bruno Luong]

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

[Benson Gou]

Dear Bruno,

Thanks a lot for your great help.

Best regards,

Benson