Hello! I have been trying to solve the problem I will describe next for a long time: given a discrete complex sequence x(n), with duration N, whose values can just be {1+j,-1+j,-1-j 1-j}, I just know the resulting signal from the correlation of x(n) with a delayed version of it (conjugating is not done, so it is not exactly the same as autocorrelation, and so the phase information is not lost), how can I recover the signal x(n)? Typical values of N are 128, 256 512 and 2048. I have tried to solve it algebraically, but the system is ill conditioned, as far I know this choice is not viable. So that, I am thinking of any kind of solution which takes advantage of knowing that the values of x(n) are independent and identically distributed, some solution near independent component analysis algorithms, but I am a little bit lost in this subject. For clarity, the signal I know is: s(0)=x(0)*x(0) s(1)=x(0)*x(1)+x(1)*x(0) s(2)=x(0)*x(2)+x(1)*x(1)+x(2)*x(0) .. s(2N-2)=x(N-2)*x(N-1)+x(N-1)*x(N-2) s(2N-1)=x(N-1)*x(N-1) Any suggestion?

# Reconstruction of a complex sequence

Started by ●December 8, 2008

Reply by ●December 9, 20082008-12-09

On Dec 8, 12:37�pm, "Crisanquito" <crisanc...@hotmail.com> wrote:> Hello! > > I have been trying to solve the problem I will describe next for a long > time: > given a discrete complex sequence x(n), with duration N, whose values can > just be {1+j,-1+j,-1-j 1-j}, I just know the resulting signal from the > correlation of x(n) with a delayed version of it (conjugating is not done, > so it is not exactly the same as autocorrelation, and so the phase > information is not lost), how can I recover the signal x(n)? Typical values > of N are 128, 256 512 and 2048. > > I have tried to solve it algebraically, but the system is ill conditioned, > as far I know this choice is not viable. So that, I am thinking of any kind > of solution which takes advantage of knowing that the values of x(n) are > independent and identically distributed, some solution near independent > component analysis algorithms, but I am a little bit lost in this subject. > > For clarity, the signal I know is: > > s(0)=x(0)*x(0) > s(1)=x(0)*x(1)+x(1)*x(0) > s(2)=x(0)*x(2)+x(1)*x(1)+x(2)*x(0) > .. > s(2N-2)=x(N-2)*x(N-1)+x(N-1)*x(N-2) > s(2N-1)=x(N-1)*x(N-1) > > Any suggestion?Your problem looks looks a radix-4 multiply with a complex number system. I'm not sure if I can help with it, but you may want to do a search for radix-r multiplication for complex numbers. Kevin

Reply by ●December 9, 20082008-12-09

Crisanquito wrote:> Hello! > > I have been trying to solve the problem I will describe next for a long > time: > given a discrete complex sequence x(n), with duration N, whose values can > just be {1+j,-1+j,-1-j 1-j}, I just know the resulting signal from the > correlation of x(n) with a delayed version of it (conjugating is not done, > so it is not exactly the same as autocorrelation, and so the phase > information is not lost), how can I recover the signal x(n)? Typical values > of N are 128, 256 512 and 2048. > > I have tried to solve it algebraically, but the system is ill conditioned, > as far I know this choice is not viable. So that, I am thinking of any kind > of solution which takes advantage of knowing that the values of x(n) are > independent and identically distributed, some solution near independent > component analysis algorithms, but I am a little bit lost in this subject. > > For clarity, the signal I know is: > > s(0)=x(0)*x(0) > s(1)=x(0)*x(1)+x(1)*x(0) > s(2)=x(0)*x(2)+x(1)*x(1)+x(2)*x(0) > .. > s(2N-2)=x(N-2)*x(N-1)+x(N-1)*x(N-2) > s(2N-1)=x(N-1)*x(N-1) > > Any suggestion?Your problem is ill posed, it has more than one solution. To see this, consider first the simple case where the x and the s sequences both have length 1, ie. s(0) = x(0)*x(0). In that case, given s there are two possible solutions for x, namely x_1(0) = complex_sqrt(s0) and x_2(0) = - complex_sqrt(s0), where the function y = complex_sqrt(z) takes the square root of z such that arg(y) = arg(z)/2 (it doesn't really matter which one you chose). For a x sequence of length 2 (s sequence length 3) you have s(0) = x(0)^2 s(1) = 2 x(1) x(0) s(2) = x(1)^2. Noting the sign of s(1), there are again two possible solutions, namely x_1(0) = complex_sqrt(s(0)) x_1(1) = complex_sqrt(s(2)) and x_2(0) = -complex_sqrt(s(0)) x_1(1) = -complex_sqrt(s(2)). And so on. Regards, Andor

Reply by ●December 9, 20082008-12-09

>Crisanquito wrote: >> Hello! >> >> I have been trying to solve the problem I will describe next for along>> time: >> given a discrete complex sequence x(n), with duration N, whose valuescan>> just be {1+j,-1+j,-1-j 1-j}, I just know the resulting signal from the >> correlation of x(n) with a delayed version of it (conjugating is notdone,>> so it is not exactly the same as autocorrelation, and so the phase >> information is not lost), how can I recover the signal x(n)? Typicalvalues>> of N are 128, 256 512 and 2048. >> >> I have tried to solve it algebraically, but the system is illconditioned,>> as far I know this choice is not viable. So that, I am thinking of anykind>> of solution which takes advantage of knowing that the values of x(n)are>> independent and identically distributed, some solution nearindependent>> component analysis algorithms, but I am a little bit lost in thissubject.>> >> For clarity, the signal I know is: >> >> s(0)=x(0)*x(0) >> s(1)=x(0)*x(1)+x(1)*x(0) >> s(2)=x(0)*x(2)+x(1)*x(1)+x(2)*x(0) >> .. >> s(2N-2)=x(N-2)*x(N-1)+x(N-1)*x(N-2) >> s(2N-1)=x(N-1)*x(N-1) >> >> Any suggestion? > >Your problem is ill posed, it has more than one solution. To see this, >consider first the simple case where the x and the s sequences both >have length 1, ie. > >s(0) = x(0)*x(0). > >In that case, given s there are two possible solutions for x, namely > >x_1(0) = complex_sqrt(s0) > >and > >x_2(0) = - complex_sqrt(s0), > >where the function y = complex_sqrt(z) takes the square root of z such >that > >arg(y) = arg(z)/2 > >(it doesn't really matter which one you chose). For a x sequence of >length 2 (s sequence length 3) you have > >s(0) = x(0)^2 >s(1) = 2 x(1) x(0) >s(2) = x(1)^2. > >Noting the sign of s(1), there are again two possible solutions, >namely > >x_1(0) = complex_sqrt(s(0)) >x_1(1) = complex_sqrt(s(2)) > >and > >x_2(0) = -complex_sqrt(s(0)) >x_1(1) = -complex_sqrt(s(2)). > >And so on. > >Regards, >Andor >Thanks Kevin, I will study it just in the case it could be useful. Andor, the problem is ill posed, that is the reason I do not want to deal with it as an system of equations. Furthermore, I forgot to say that the samples of x(n) are corrupted, which complicates more the algebraic solution. So I thought maybe there could be some statistical approach, considering that the number N could considerably high. Thanks and regards.

Reply by ●December 9, 20082008-12-09

On 9 Dez., 14:44, "Crisanquito" <crisanc...@hotmail.com> wrote:> >Crisanquito wrote: > >> Hello! > > >> I have been trying to solve the problem I will describe next for a > long > >> time: > >> given a discrete complex sequence x(n), with duration N, whose values > can > >> just be {1+j,-1+j,-1-j 1-j}, I just know the resulting signal from the > >> correlation of x(n) with a delayed version of it (conjugating is not > done, > >> so it is not exactly the same as autocorrelation, and so the phase > >> information is not lost), how can I recover the signal x(n)? Typical > values > >> of N are 128, 256 512 and 2048. > > >> I have tried to solve it algebraically, but the system is ill > conditioned, > >> as far I know this choice is not viable. So that, I am thinking of any > kind > >> of solution which takes advantage of knowing that the values of x(n) > are > >> independent and identically distributed, some solution near > independent > >> component analysis algorithms, but I am a little bit lost in this > subject. > > >> For clarity, the signal I know is: > > >> s(0)=x(0)*x(0) > >> s(1)=x(0)*x(1)+x(1)*x(0) > >> s(2)=x(0)*x(2)+x(1)*x(1)+x(2)*x(0) > >> .. > >> s(2N-2)=x(N-2)*x(N-1)+x(N-1)*x(N-2) > >> s(2N-1)=x(N-1)*x(N-1) > > >> Any suggestion? > > >Your problem is ill posed, it has more than one solution. To see this, > >consider first the simple case where the x and the s sequences both > >have length 1, ie. > > >s(0) = x(0)*x(0). > > >In that case, given s there are two possible solutions for x, namely > > >x_1(0) = complex_sqrt(s0) > > >and > > >x_2(0) = - complex_sqrt(s0), > > >where the function y = complex_sqrt(z) takes the square root of z such > >that > > >arg(y) = arg(z)/2 > > >(it doesn't really matter which one you chose). For a x sequence of > >length 2 (s sequence length 3) you have > > >s(0) = x(0)^2 > >s(1) = 2 x(1) x(0) > >s(2) = x(1)^2. > > >Noting the sign of s(1), there are again two possible solutions, > >namely > > >x_1(0) = complex_sqrt(s(0)) > >x_1(1) = complex_sqrt(s(2)) > > >and > > >x_2(0) = -complex_sqrt(s(0)) > >x_1(1) = -complex_sqrt(s(2)). > > >And so on. > > >Regards, > >Andor > > Thanks Kevin, I will study it just in the case it could be useful. > > Andor, the problem is ill posed, that is the reason I do not want to deal > with it as an system of equations.Ill posed in this case means that there is no unique solution (even in the noiseless case). You worte that the algebraic approach was "ill conditioned", not at all the same thing (you can circumvent the latter, never the former).> Furthermore, I forgot to say that the > samples of x(n) are corrupted, which complicates more the algebraic > solution. > So I thought maybe there could be some statistical approach, > considering that the number N could considerably high.Do you have a solution that works for your required N in the noiseless case? If not, start there, then try to handle the noise in the next step. Regards, Andor