# A set of Quadratic equation, any good algorithm?

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.

-

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.

-
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? –  DavidBear 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? –  DavidBear 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. –  DavidBear Jan 20 '13 at 15:43