6
$\begingroup$

Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A B$. Formally,

$$\underset{A \in \mathbb{C}^{n \times n}}{\text{minimize}} \quad \frac{1}{2} \|AB\|_F^2 \quad \text{subject to} \quad \det (A) \neq 0$$

The value of $m$ is typically an order of magnitude larger than $n$. The sizes ($n,m$) I am interested in may be on the order of hundreds.

I have found the following discussion, which I guess could be generalized to the above case. I wonder if there is a simpler solution in this particular scenario.

Improve this question
$\endgroup$
15
  • 5
    $\begingroup$ There needs to be a stronger constraint than just $\det A \neq 0$. Otherwise given any ``optimal'' $A$, you can get a better solution still satisfying the constraint by scaling $A$ down, like $\frac{1}{2}A$. $\endgroup$
    – Nick Alger
    Commented Aug 16, 2018 at 1:16
  • 2
    $\begingroup$ The question to answer here is whether the set of invertible matrices is bounded and closed (i.e., compact) in the space ${\mathbb R}^{n\times n}$ equipped with the Frobenius norm. Using the example in @user7440's comment, if the set of invertible matrices is not compact, then you can find a sequence $A_k$ of invertible matrices whose norm $\|A_k\|_F$ decreases as $k\rightarrow 0$ but which does not converge in the set of invertible matrices. $\endgroup$
    – Wolfgang Bangerth
    Commented Aug 16, 2018 at 14:48
  • 2
    $\begingroup$ Indeed, take the simplest case, $n=1$, and consider the sequence $A_k=\frac{1}{k}$. These matrices are invertible, their Frobenius norm decreases and converges to zero, but the limit point $A=0$ is not a set of invertible matrices. $\endgroup$
    – Wolfgang Bangerth
    Commented Aug 16, 2018 at 14:51
  • 2
    $\begingroup$ If you add your constraint $\|A\|_F=1$, you need to go to $n=2$, where I posit the following sequence: $A_k = [[ \sqrt{1-1/k}, 0], [0, \sqrt{1/k}]]$. All of these are minimizers of the original problem with the special choice $B$, and all are invertible, but the limit point is not invertible. $\endgroup$
    – Wolfgang Bangerth
    Commented Aug 16, 2018 at 14:54
  • 3
    $\begingroup$ In other words, the statement $\text{det}\ A \neq 0$ is not something you can enforce in actual computations because it excludes too few matrices (essentially none). A statement such as $|\text{det}\ A| > 0.1$, on the other hand, makes sense. $\endgroup$
    – Wolfgang Bangerth
    Commented Aug 16, 2018 at 22:37

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.

Browse other questions tagged or ask your own question.