QR-Decomposition of matrix valued function

Question

Suppose I have a matrix valued function

$$ F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T $$ where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, $\tilde R\in\mathbb{R}^{m\times n}$ upper triangular, $u_1,u_2\in\mathbb{R}^m$ and $v_1,v_2\in\mathbb{R}^n$.

Is there anything that can be said about the QR decomposition of $F(x)=Q(x)R(x)$ depending on $x$?

---

To give a bit more background: I would like to minimize $$ g(x)=||Q^T_2(x)z||^2_2 $$ for some vector $z \in \mathbb{R}^{m} $ and $$ F(x)=Q(x)R(x)=\begin{bmatrix}Q_1(x)& Q_2(x)\end{bmatrix}\begin{bmatrix}R_1(x)\\0\end{bmatrix}=Q_1(x)R_1(x). $$

I plotted the function $g$ for a few different cases, and it always looks similar to this:

I have been wrapping my mind around the following two questions:

• Is it just coincidence that I see exactly one local minimum and one local maximum, or might that be proven?
• Might it even be possible to give a direct algorithm that finds the minimum of this function?

It is not to difficult to employ a nonlinear optimizer to find the minimum, however, in that case I would like the guarantee that I in fact only have one local minimum and that my optimizer in case it does not diverge is ensured to find the global optimum.

---

What I have tried: There are algorithms for updating a QR decomposition with rank 1 matrices, e.g. by Daniel, Gragg, Kaufman and Stewart. I tried to follow those steps symbolically but using a series of Givens Rotations to ensure triangularity of a the matrix $R(x)$ quickly leads to terms that I found not to be good to handle. However, maybe I am just missing a good idea for a clear notation or do not see the system behind.

Any help (even if it is just a pointer to a paper that does something similar) is greatly appreciated.

Answer 1

It is hard to say anything about the QR decomposition of $F(x)$ but I think I can help you with the optimization problem.

I suppose that the dimension of $z$ is fix and given by $m-n$. It is not difficult to show that $g(x)=||Q_2(x)z||^2_2=||z||^2$: Let us define $\tilde{z} = [0^T,z^T]^T$, where $0$ is the $m$-dimensional zero vector. Then, $||{z}||^2_2 =||\tilde{z}||^2_2 = ||Q(x) \tilde{z}||^2_2 = ||Q_1(x)0||^2_2 +||Q_2(x)z||^2_2 = ||Q_2(x)z||^2_2$. In the second equation I have exploited that $Q(x)$ is orthonormal.

Therefore, $g(x)$ does not depend on $x$.

Answer 2

I finally figured why the graph of my function always looks like the one above. However, it turns out that this is no general property of rank one matrices, but strongly depends on sparsity of the vectors $v_1$ and $v_2$ that in my situation always is valid.

The fully formal discussion of the matter now takes about 5 pages, which I will not write down in full detail here. However, I will sketch the main idea:

Let us assume $v_1=e_j$ and $v_2=e_{j'}$ where $e_i$ is the $i$-th unit vector, which is my situation. The argument below would also work for vectors that are different to zero at two identical entries. For three or more entries it is still possible, but the complexity increases exponentially.

Now let $P$ a permutation matrix that exchanges the columns $j$ and $j'$ to the last two columns of $v^T_1P$ and $Pv^T_2$. Then $$ \tilde Q^T F(x)P=\tilde R P+xu_1v^T_1P+xu^T_2v^T_2P=\tilde RP+xu_1e^T_{n-1}+xu_2e^T_{n} $$ is upper triangluar everywhere but the remaining two rows.

Now we can find a matrix $\hat Q$ such that $$ \hat Q\begin{bmatrix}u_1&u_2\end{bmatrix}=\begin{bmatrix} ?_n & ?_n \\ 0_{m-n} & e_1\end{bmatrix}\qquad \text{and} \qquad \hat Q\tilde R=\tilde R $$ where $?_n$ are arbitrary but known vectors in $R^n$. Then $$ \hat Q\tilde Q^T F(x)P=\tilde RP+x\hat Qu_1e^T_{n-1}+x\hat Qu_2e^T_{n} $$ only differs at two entries from upper triangular.

Those entries now can be eliminated using two Givens Rotations depending on $x$. This requires some effort but is absolutely doable with symbolic reformulations.

Altogether we found a $QRP$ decomposition of $F(x)$ that only depends in two Givens rotations on $x$. Evaluating the norm in my optimization problem (that is not bothered by the matrix $P$) I get a rational function with numerator and denominator of degree 2.