How can I solve this linear System?

Lets say I have

   A    *    x   =    b 
  n*n       n*1      n*1
 Unknown   known    known

A is unknown but it is known to be a symmetric Toeplitz matrix. eg:

 [ 5 2 0 7 ;

   2 5 2 0 ; 

   0 2 5 2 ;

   7 0 2 5 ]

How Can I find A?

Thanks in advance.

Saeed

[Saeed]

Is there a Matlab function that can perform this task?

Answer 1

[Andrei Bobrov]

eg:

x = rand(4,1);
b = rand(4,1);

solution

nn = 1:numel(x);
n = nn(end);
idx = abs(bsxfun(@minus,nn,nn')) + 1;% OR idx = toeplitz(nn);
id1 = arrayfun(@(ii)accumarray((idx(ii,:))',nn',[4 1],@(x){x}),nn,'un',0);
id1 = [id1{:}].';
Xmtx = cellfun(@(z)sum(x(z)),id1);
Av = Xmtx\b;
A = Av(idx);

check

all(abs(A*x-b)<100*eps)

[Teja Muppirala]

Wow.

[Saeed]

Thanks

Answer 2

[Richard Brown]

And another way (which could be chained into a very long one-liner). First, assuming you have the following test data:

% Test data
n = 4;
x = rand(n, 1);
b = rand(n, 1);

It's only a couple of lines:

B = toeplitz(x,x(1)*eye(1,n)) + fliplr(toeplitz(x(end)*eye(1,n), flipud(x)));
B(:,1) = 0.5 * B(:, 1);
A = toeplitz(B \ b);

[Andrei Bobrov]

+1

[Saeed]

Thanks

Answer 3

[Jan]

At first you can convert this into a linear system:

A = [a, b, c, d; ...
     b, a, b, c; ...
     c, b, a, b; ...
     d, c, b, a];

Then multiply this with your known x and b to obtain a standard linear problem with the unknowns [a,b,c,d] in a vector.

[Saeed]

So I have no choice but use n syms?

[Jan]

Instead of syms, you can write this down *on paper* and solve it manually at first. Then you will find some pattern, which allows to solve it programmatically also.

[Saeed]

Thanks I did this, and the pattern is quite interesting.

Answer 4

[Saeed]

 B = tril(toeplitz(x))
 A = toeplitz(B(:,1) + hankel(x))\b)

[Andrei Bobrov]

A = toeplitz(bsxfun(@rdivide,tril(toeplitz(x))+hankel(x),eye(1,numel(x))+1)\b)

[Richard Brown]

punk :p