Generate a semi-unitary matrix I would like to generate a semi-unitary matrix, i.e., $UU^T=~I$ where U is a non-square matrix whose number of rows is bigger than its number of columns.
I tried it by solving the optimization problem $\min_U\|UU^T - I\|_F$ but didn't work at all since the problem is not convex. 
 A: If you want to have $UU^T = I$, you need is a matrix with more columns than rows, and whose rows are length-$1$ and mutually orthogonal.
Otherwise, the best you can do is find a matrix such that
$$
UU^T = \pmatrix{I_r & 0\\0&0}
$$
where $r$ is the rank of $U$ (i.e. the number of columns).
A: Consider the simplest nontrivial case of this problem: you want 
$$
U = \begin{bmatrix}
a\\b
\end{bmatrix}
$$
with 
$$
UU^T = \begin{bmatrix}
1 & 0\\0 & 1
\end{bmatrix}
$$
i.e.,
$$
\begin{bmatrix}
a^2  & ab \\ba & b^2
\end{bmatrix} = 
\begin{bmatrix}
1 & 0\\0 & 1
\end{bmatrix}
$$
Which requires that both $a$ and $b$ square to $1$, so each is $\pm 1$, but $ab = 0$; that's impossible.
A fancier explanation (for the general $n \times k$ problem) uses three helpful theorems:


*

*$rank(AB) \le max(rank(A), rank(B))$, 

*the rank of an $n \times k$ matrix is no more than $min(n, k)$. 

*$rank(A^T) = rank(A)$. 
In your case, $k$ is the smaller number (more rows that cols), so the second and third tell you that $rank(U) = rank(U^T) \le k$; then the first tells you that $rank(UU^T) \le k$. But $rank(I_n) = n$, so you have a contradiction. 
This latter argument is the one many mathematicians would make -- in its short form, it reads "the rank of the left side is no more than $k$, but the rank of the right is $n$, so it's impossible." 
But the former argument is the result of a really useful approach to problems like this in linear algebra: try the 2 or 3 simplest cases, and see whether you can come up with something. If not, there's a decent chance there's no solution, or that the solutions for a low-dimensional subspace (or submanifold) of the domain; low-dimensional within a 2-, 3-, or 4-dimensional domain means "often not too hard to solve/check/examine by hand," and you can gain some real insight from this. I'd guess that half my answers to linear algebra questions on MSE follow this approach (often, like this one, hoping to instruct the questioner about how s/he might solve his/her own problems in the future). 
You can also do numerical experiments: try 100,000 random $2 \times 1$ matrices and see whether any of them have $UU^t = I_2$. Pretty rapidly you'll notice a pattern. If there were a solution, even in a low-dim subspace, one of your test cases would likely have been near that subspace, so that the difference $UU^T - I$ would be small. If in all your examples, there's an entry of $UU^T - I$ that's at least, say, 1/2, then you're really unlikely to find a solution, and it's time to switch efforts from "I want to find a $U$ with this property" to "I want to prove that not such $U$ exists."
