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.

$\endgroup$
  • 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 Aug 16 '18 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 Aug 16 '18 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 Aug 16 '18 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 Aug 16 '18 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 Aug 16 '18 at 22:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.