1
$\begingroup$

I have a matrix $F ∈ \mathbb{C}^{(m × N)}$, where $m < N$, and $F \times F^H$ is a unitary $m × m$ matrix.

I need to find a unitary matrix $G$ with a dimension of $N × N$ such as results of $F\times G=0$ with dimension $m \times m$ or at least the result is minimum.

So, does the matrix $G$ can be found directly or it must to be optimized? If optimized, can I proof that is always exist?

Edit with Matlab example

Let's have an example of the matrix $F$ as follows:

clear all; clc; 
F = [0.3536 - 0.1464i  -0.3536 - 0.8536i  -0.3536 + 0.8536i   0.3536 + 0.1464i   0.5000 + 0.5000i   0.5000 - 0.5000i; -0.3536 - 0.8536i   0.3536 - 0.1464i   0.3536 + 0.1464i  -0.3536 + 0.8536i   0.5000 - 0.5000i   0.5000 + 0.5000i]; 
[U, sigma, Vh] = svd(F); 
% e = ....
G = Vh'*e; 

How to define the matrix $e$ to make $V*sigma*Vh = 0$?

$\endgroup$
6
  • $\begingroup$ I'm not sure to understand everything you say but since $F \times F^{H}$ is invertible and of size $m\times m$ and you're looking for the kernel of F I assume you have $m<N$. Therefore in that case your kernel is exactly of dimension $N-m$. I'm pretty confident you can figure out something very quickly by looking at the singular value decomposition of $F$. Is this homework? $\endgroup$
    – NokiYola
    Sep 26, 2023 at 7:24
  • $\begingroup$ Hey was my comment helpful? Do you have new developments or some additional precision to help us understand your problem? $\endgroup$
    – NokiYola
    Sep 27, 2023 at 12:27
  • $\begingroup$ @NokiYola Firstly, that is not homework, it's a issued which is related to my area of research I try to solve it. Yes I got your point about the singular value decomposition, but that cannot be solved using SVD as the $m < N$. For the misunderstanding of my question, I am sorry for that. But, that can summurized that I need to find the matrix $G$ such that $F \times G$ is null or at least minimum. Using the SVD is not possible as the $m < N$. $\endgroup$
    – Fatima_Ali
    Oct 6, 2023 at 15:18
  • $\begingroup$ Hello there. I'll post my answer then and you'll tell me what is wrong in my reasoning. Maybe if we're two we'll solve your problem. I don't understand what you mean by "at least the result is minimum". $\endgroup$
    – NokiYola
    Oct 11, 2023 at 12:36
  • $\begingroup$ @NokiYola I mean by "at least the result is minimum" is to have the $F \times G$ is zero or a very small values which are near to zero. $\endgroup$
    – Fatima_Ali
    Oct 14, 2023 at 4:59

1 Answer 1

3
$\begingroup$

Here is an attempt, tell me what I misunderstood.

You say that $F\times F^{H}$ (which is of dimension $m\times m$ ) is unitary, which implies it is invertible. Therefore it means that $F$ is of full rank, i.e $rank(F) = m$.

From that we know from the rank nullity theorem that $ker(F)$ will be of dimension $N-m$. This means that no matter how hard you try, you won't find more than $N-m$ independent vectors $d_i$ such that $F \times d_i = 0$. This seriously compromise the existence of a G of size $N\times N$. Instead it will be of size $N\times(N-m)$.

Now how to find such a G matrix? For what I understand of singular value decomposition it exists no matter what are the dimensions of your matrix. In particular it exists if $m<N$. So we can write:

$$F = U\Sigma V^{H}\tag{1}\label{eq1}$$ with $U$ of dimension $m\times m$ unitary, $V$ of dimension $N\times N$ and also unitary. We know from the fullness of $F$'s rank that

$$\Sigma = \begin{bmatrix} diag(\lambda_1, ..., \lambda_m) && 0_{m\times (N-m)}\end{bmatrix}\tag{2}\label{eq2}$$

with $\lambda_1$, ..., $\lambda_m$ all nonzero.

Now if you multiply $\Sigma$ by :

$$e_{m+p} = \begin{bmatrix}0\\0\\...\\0\\ 1\\0\\...\\0 \end{bmatrix}\tag{3}\label{eq3}$$

with the $1$ at the n+p-th position and $1\leq p\leq N-m$ we get $0$. From that with $$G = V\times \begin{bmatrix}e_{m+1}, e_{m+2}, ..., e_N\end{bmatrix}\tag{4}\label{eq4}$$

you get

$$F\times G = U\Sigma V^{H} \times V\times\begin{bmatrix}e_{m+1}, e_{m+2}, ..., e_N\end{bmatrix} = U \begin{bmatrix}\Sigma e_{m+1},\Sigma e_{m+2}, ..., \Sigma e_N\end{bmatrix} = 0 \tag{5}\label{eq5}$$ One can easily verify : $$(Ve_{n+i})^{H}\times (Ve_{n+j}) = e_{n+i}^Te_{n+j} = \delta_{ij} \tag{6}\label{eq6}$$

So that the $Ve_{n+k}$ with $1\leq k\leq N-m$ form an orthonormal basis of $ker(F)$ which is the closest thing you can get from the G you specified.

I also found something else : Since you said $F\times F^{H}$ is unitary, using the SVD decomposition from \ref{eq1} the unitary nature of $F\times F^{H}$ we get : $$F\times F^{H}\times F\times F^{H} = U\Sigma V^{H}V\Sigma^{H} U^{H}U\Sigma V^{H}V\Sigma^{H} U^{H} = U (\Sigma\Sigma^{H})^{2} U^{H} = I_{m\times m}\tag{7}\label{eq7}$$

This yields $$(\Sigma\Sigma^{H})^{2}= I_{m\times m}\tag{8}\label{eq8}$$

from \ref{eq2} we easily get $$\Sigma\Sigma^{H} = diag(\vert\lambda_1\vert^{2}, \vert\lambda_2\vert^{2}, ..., \vert\lambda_m\vert^{2})\tag{9}\label{eq9}$$ Therefore \ref{eq7} translates into :

$$diag(\vert \lambda_1\vert^{4}, \vert \lambda_2\vert^{4}, ..., \vert \lambda_m\vert^{4}) = I_{m\times m}\tag{10}\label{eq10}$$

which finally means $$\vert\lambda_i\vert =1\quad\forall 1\leq i\leq m\tag{11}\label{eq11}$$

I found it interesting.

If this does not answer your question please tell us what you mean by "at least the result is minimum" (which result? minimum in what regards?). Also could you detail what you mean by "can be found directly or it must to be optimized"? Anyway I hope it helped you one way or another.

Edit : You seem to be interested in convergence properties so I went back looking at how SVD works (I had forgotten). In a naive algorithm (like if I had to implement it from scrathes myself today) I would have to compute $A\times A^{H}$, then the eigen elements of this matrix (using the so-called QR algorithm, which is a converging and to my knowledge pretty stable algorithm).

The eigenvectors would give me the U matrix, Then I'd multiply $A^{H}$ with some of those eigenvectors (those associated with nonzero eigenvalues) and complete this into a orthonormal basis of $\mathbb{R}^m$ and this would give me V. and the last $m-r$ (where $r = rank(A)$) vectors of V would give G.

So the most numerically perilous parts here seem to be the computation of $A\times A^{H}$ and then the computation of the $A^{H} U_i$ (with $U_i$ the ad hoc columns of $U$).

That being said here is a code made in python checking the computation of G using numpy's SVD and the errors made computing $A\times G$.

I simplified a bit, multiplying by the e matrix is equivalent to selecting its last (N-m) columns

import numpy as np

n = 100
m = 1000
A = np.random.rand(n, m)
svd_decomposition = np.linalg.svd(A)

U = svd_decomposition[0]
V = svd_decomposition[2].T

r = np.linalg.matrix_rank(A)
G = V[:, r:]
res = np.abs(A@G).sum()
print(res)

with the columns and row numbers I set I get something in the 10-12 realm. The error seem to grow with the number of rows but is pretty insensitive to the number of columns.

$\endgroup$
5
  • $\begingroup$ I mean can we calculate the value of $G$ directly or we need to find it by optimization to make $F \times G$ a values which is small values near to zero. I will try to understand your answer and let you know. $\endgroup$
    – Fatima_Ali
    Oct 14, 2023 at 5:03
  • $\begingroup$ I agree with your solution, but I couldn't get your idea how to build the matrix $e_{m+p}$. I added an example for the matrix $F$ and how to get matrices mentioned using SVD, So, Could you please help how to build the matrix $e$ ? $\endgroup$
    – Fatima_Ali
    Oct 15, 2023 at 12:01
  • $\begingroup$ Thank you for your reply, but it seems the matrix $G$ in this case is not unitary. In your case, its dimension is of $1000 \times 100$. What I am looking for it is to have a unitary matrix $G$. I hope the question is clearer now $\endgroup$
    – Fatima_Ali
    Oct 15, 2023 at 12:34
  • $\begingroup$ Did you get my Idea ? $\endgroup$
    – Fatima_Ali
    Oct 17, 2023 at 3:21
  • $\begingroup$ @Fatima_Ali I edited my post, I had a mishmash in my code and G wasn't the size I expected. However I already answered, G, in our case, can't be of dimension 1000x1000 because of the rank nullity theorem (check out the link in my post). It can be, at best, 1000x900. In fact with the same theorem one could show that to have a 1000x1000 invertible G such that $F\times G = 0$ means that $F=0_{m\times N}$. Besides, my G is close to unitary in the sense that $G^TG=I_{900\times 900}$. It's theoretically impossible to do better. So either your problem is solved or something is missing in it. $\endgroup$
    – NokiYola
    Oct 17, 2023 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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