2
$\begingroup$

Let $A\in\mathbb{R}^{m\times n}$ be a full column rank matrix. Then there exists a left inverse $A^+$ of $A$. Let $w\in \mathbb{R}^n$ be a vector. Is there a closed-form solution for the following problem?

$$ \begin{aligned} \min\limits_{A^+} \ & \|{A^+}^Tw\|_1\\ \text{s.t.} \ & A^+A= I \end{aligned} $$

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't know about a closed form, but this should be efficiently computable by linear programming -- would that help? You could also use LP duality to get analytic lower bounds on this quantity. $\endgroup$
    – Nathaniel Johnston
    Commented Nov 13, 2019 at 15:13
  • $\begingroup$ I'm well aware that this can be efficiently solved. I'm interested in a closed-form because in the problem I'm working on, $w$ would be a decision variable along with $A^+$ $\endgroup$
    – brachester
    Commented Nov 13, 2019 at 16:44
  • 1
    $\begingroup$ For what it's worth, it would be rather shocking if a closed-form solution exists. 1-norm minimization is one of the standard examples of how linear programming is useful. We can do 2-norm minimization in closed form, but 1-norm and infinity-norm minimization seem to require something slightly more. $\endgroup$
    – Nathaniel Johnston
    Commented Nov 14, 2019 at 12:34

1 Answer 1

Reset to default
2
$\begingroup$

If $B$ is one left inverse of $A$, then $B+X$ is a left inverse of $A$ (where $X$ is $n \times m$) iff $X A = 0$, i.e. the restriction of $X$ to $\text{Ran}(A)$ is $0$. Of course if $A$ is surjective, there is no choice: $X$ must be $0$, so let's suppose it is not. We may also assume $w \ne 0$.

We can choose $X$ so that $X^T w$ is any member of $\text{Ran}(A)^\perp = \text{Ker}(A^\top)$. So the question is reduced to: find $v \in \text{Ker}(A^\top)$ to minimize $\|B^\top w + v\|_1$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .