3
$\begingroup$

Is there a fast method to compute an orthogonal complement of an arbitrary matrix $U\in\mathbb{R}^{m \times n}$ in BLAS / LAPACK?

Specifically, I want any matrix $V\in \mathbb{R}^{m \times (m - \text{rank}(M))}$ such that $$ \text{rank}(U|V) = m. $$

The singular value decomposition methods in LAPACK can do this if called correctly, but if $U\in\mathbb{R}^{m \times (m-1)}$ is full rank, this will take $O(m^3)$, when it should only take $O(m^2)$ (e.g., via Gram-Schmidt orthogonalization of a random vector).

Orthogonality of $V$ is a plus but not required.

Improve this question
$\endgroup$
7
  • $\begingroup$ Are you assuming $U$ has orthogonal columns? Otherwise I don't think a Gram-Schmidt-type algorithm would be guaranteed to work. $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2022 at 7:40
  • $\begingroup$ @Federico, good point. I didn't really mean to assume that. And I guess the only practical situation where I'd know I have orthogonal columns would be after just having run an $O(m^3)$ algorithm like "non-full" SVD or QR $\endgroup$
    – Bananach
    Commented Nov 2, 2022 at 8:39
  • $\begingroup$ I mean, I don't think running a Gram-Schmidt-like process ensures that you get a valid solution, unless $U$ was already orthogonal to start with. So I'm not sure that there is a $O(m^2)$ solution as you claim in the case $n=m-1$. $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2022 at 10:05
  • $\begingroup$ And then the next question is: can you assume $U$ to have full column rank? Otherwise, checking it requires $O(mn^2)$ to start with. $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2022 at 10:06
  • $\begingroup$ (And let me also note that in practice in this case taking a random $V$ works with probability 1!) $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2022 at 10:07

0

Reset to default

Your Answer

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