Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

now I'm doing my research on filter design and I'm stuck in a mathematic problems. I want to solve the following equation:

$\sum_{k_{1}=0}^{N-L-K}\sum_{k_{2}=0}^{N-L-K}\alpha_{k1}\alpha_{k2}d_{k_{1},k_{2}}(2n)=\delta(n).$

where, $L,K,N$ are constant and $d_{k_{1},k_{2}}(2n)$ is also known. We want to obtain $\alpha_{k}$. Obviously, the question can be extended into a set of quadratic constraints equations. I have read some paper by using LSE method.

Now I want to directly solve this equation, i.e., do not use an optimise method. Is there some algorithm on solving such problem? Thank all you guys in advance.

share|improve this question
add comment

1 Answer

In general, we can write, using $\mathbf{x} = \pmatrix{x_0 & x_1 & \ldots}$ and $\mathbf{y}=\pmatrix{y_0 & y_1 & \ldots}^\top$ $$\mathbf{x}G\mathbf{y} = \sum_{i=1}^m\sum_{j=1}^n x_iy_jg_{ij}$$ where $G$ is conformable (has the correct dimensions with $m$ rows and $n$ columns.)

Thus for your equation $$\sum_{k_{1}=0}^{N-L-K}\sum_{k_{2}=0}^{N-L-K}\alpha_{k1}\alpha_{k2}d_{k_{1},k_{2}}(2n)=\delta(n)$$ you have $$ \mathbf{\alpha_1}D_{2n}\mathbf{\alpha_2} =\delta(n) $$

where $$\mathbf{\alpha_1} = \pmatrix{\alpha_{k1} & \alpha_{k1} & \ldots}$$ and $$\mathbf{\alpha_2} = \pmatrix{\alpha_{k1} \\ \alpha_{k1} \\ \vdots}$$ and $D_n = [d_{k_1,k_2}(n)]$ the matrix with elements from $d_{k_1,k_2}$. In words, the $\alpha_{k1}$ scale the $k_1$ row elements, so it is a left multiply. Similarly, $\alpha_{k2}$ scales the column elements, so it is a right multiply.

This would be what is called a quadratic form if you have $\mathbf{y}=\mathbf{x}^\top$. I have to assume that your problem is not quite the same there as you use separate indices on $\alpha$. But at the same time you use the same $\alpha$ which implies $\alpha_{k1}$ may be the same as $\alpha_{k2}$ but in a different order. This would be true for example if your elements $k_1$ and $k_2$ comprised each element of the same set. If this is the case, with the correct ordering you do have a quadratic form.

Quadratic forms behave nice in one particular manner in that there is implied symmetry. To see this write (using $H=\frac{1}{2}G + \frac{1}{2}G^\top$ and $S=\frac{1}{2}G - \frac{1}{2}G^\top$) $$G = H + S$$ giving \begin{align} \mathbf{x}G\mathbf{y} &=\mathbf{x}\left(H+S\right)\mathbf{y}\\ &= \mathbf{x}H\mathbf{y}+\mathbf{x}S\mathbf{y}\\ & = \end{align} and (using $H^\top = H$ and $S^\top = -S$) \begin{align} \left(\mathbf{x}G\mathbf{y}\right)^\top &=\mathbf{y}^\top\left(H-S\right)\mathbf{x}^\top\\ &= \mathbf{y}^\top H\mathbf{x}^\top-\mathbf{y}^\top S\mathbf{x}^\top\\ & = \end{align}

Since $\mathbf{x}G\mathbf{y}$ is a scalar, the two are the same number, and you may take the sum and divide by two. Doing such would cancel the skew symmetric portion $S$ of $G$ again if you have $\mathbf{y}=\mathbf{x}^\top$.

Lets continue from here as if you want to solve $\mathbf{x}G\mathbf{x}^\top$ where $G$ is symmetric. Factor $G=LL^\top$ using the Cholesky factorization. $$\mathbf{x}LL^\top\mathbf{x}^\top = \mathbf{x}L\left(\mathbf{x}L\right)^\top = \delta(n)$$

I think I will let you take it from here with the hope that your problem is served with the treatment thus given.

share|improve this answer
    
To @adam W: Hey adam, thx for the comments. It is really meaningful to me. But I'm still wondering that although we have obtained the last equation, but it is still a quadratic form. Therefore, it is still hard to solve. Am I right? –  Wang David Jan 20 '13 at 13:18
    
another question is that, $G=LL^{T}$ by using Cholesky factorization. If the matrix is not positive, this method can not be adopted, right? –  Wang David Jan 20 '13 at 14:07
    
@Wang To be honest, I am not too practiced in the quadratic form. For example, I am still uncertain if a full similarity (full eigen-decomposition) on $G$ is necessary or not in order to solve $\mathbf{x}G\mathbf{x} = 0$ given symmetric $G$. I would ask that as a question, but want to do the due diligence studying before asking... –  adam W Jan 20 '13 at 15:29
    
thank you for the comment. So I have to search for the algorithm for solving such system of quadratic equations. But you give me a new idea to deal with this. –  Wang David Jan 20 '13 at 15:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.