I am trying to solve a problem which is associated with Householder transformation.
I know that given an unit complex vector $v$, I can get a Householder matrix $P = I-2vv^t$. And $P$ is unitary and Hermitian, and its computational complexity is $O(N)$ rather that $O(N^2)$.
My question is, given an unitary and Hermitian complex matrix, can I find a general solution for vector $v$? Does $v$ always exist?
Also, is there any other transformation that also has a lower computational complexity similar to Householder transformation?
$\endgroup$1 Answer
$\begingroup$First of all, a quick correction to your use of terminology. It doesn't make sense to say that $P$ has computational complexity $O(N)$; $P$ is a box of numbers, not a process. It is true, however, that multiplication by P or the transformation associated with $P$ can be implemented with complexity $O(N)$.
Your question, as it is currently stated, makes no sense. However, I think that you are trying to ask the following:
Given a unitary and Hermitian complex matrix $P$, can I find a general solution for vector $v$, where $P = I - vv^*$? Does $v$ always exist?
Keep in mind that $v^*$ denotes the conjugate-transpose (as opposed to simply taking the transpose $v^T$) of $v$.
With that said: it is not true that such a $v$ will generally exist. That is, most Hermitian and unitary matrices are not Householder transformations. Geometrically, the Householder transformations correspond to reflections across a single hyperplane whereas the Hermitian-unitary matrices correspond to all possible reflections (for instance, the reflection through the origin, which would be a rotation for $N = 2$).
If a solution does exist, then we can find it as follows: let $P$ be a Householder matrix. If $u$ is any non-zero column of $I - P$, then the normalized vector $v = \frac{u}{\|u\|}$ is such that $P = I - 2vv^*$.
If we want to write a general Hermitian-unitary matrix in a compact way, we could note that there must exist a unitary matrix $V$ such that$$ P = V\pmatrix{I_{N-r} &0\\0& -I_r}V^*. $$If we partition $V$ into block-columns so that $V = [V_1 \quad V_2]$ and $V_2$ has $r$ columns, then $$ P = V_1 V_1^* - V_2V_2^* = (V_1V_1^* + V_2V_2^*) - 2V_2V_2^* = I_{N} - 2V_2V_2^*. $$When $r=1$, this is the usual expression for a Householder matrix. Once we have such a decomposition for $P$, then multiplication by $P$ can be performed with complexity $O(N)$. We could use the form $P = I_{N} - 2V_2V_2^*$ directly, or we could implement multiplication by $P$ has a $r$ successive multiplications by the Householder transformations corresponding to the columns of $V_2$.
Another commonly used transformation that has a similar "low-complexity" property is the Givens rotation.
$\endgroup$
