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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.