0
$\begingroup$

Let $\bar{y} = \frac{A\bar{x} +\bar{b}}{\bar{c}^{T}\bar{x} + d}$, where $A$ is $n \times m$ matrix with $n, m \in \mathbb R_{+}$. Let $f(x) := \bar{y}$ so $f : \mathbb R^{m} \mapsto \mathbb R^{n}$. The denominator and numerator are convex and affine so $\bar{y}$ must be convex and affine because $\bar{y}$ is essentially a perspective function with affine and convex functions. $d \in \mathbb R$ is scalar.

I want to calculate its inverse.

Switch $\bar{x}$ to $\bar{y}^{-1}$ and $\bar{y}$ to $\bar{x}$ and solve.

$$\bar{x}(\bar{c}^{T}\bar{y}^{-1}+d) - A\bar{y}^{-1} - \bar{b} = 0$$

$$(\bar{x} \bar{c}^{T} - A ) \bar{y}^{-1} + (\bar{x} d - \bar{b} ) = 0$$

So

$$\bar{y}^{-1} = (\bar{x} \bar{c}^{T} -A)^{-1}(\bar{b} - \bar{x} d)$$

if $(\bar{x} \bar{c}^{T} -A)$ is invertible.

Alert:

$$\bar{x}(\bar{c}^{T}\bar{y}^{-1}) = (\bar{x}\bar{c}^{T})\bar{y}^{-1}$$ where $c^{T}\bar{y}^{-1}$ is contant but the dimensions with $\bar{x}\bar{c}^{T}$ may not match. Something very wrong here, any rescue? Evidently I should have certain assumptions about the dimensions so that the operations above are correct. Is there some easy way to find the inverse mapping for the function $\bar{y}$?

  • 0
    How did you get from the first line to the second?2011-09-20
  • 0
    @RahulNarain: now understable? Corrected a random err.2011-09-20
  • 1
    You cannot "divide" by a matrix. You can multiply by its inverse if it exists, so more appropriate would be $y^{-1} = (xc^T - A)^{-1}(xd - b)$.2011-09-20
  • 0
    @ThijsLaarhoven: yes, you are right about that. Now more correct?2011-09-20
  • 1
    @hhh: Actually, no. If $Ax = b$, then we can isolate $x$ by multiplying both equations with $A^{-1}$ *from the left*. So then $x = (A^{-1}A)x = A^{-1}(Ax) = A^{-1}b$. You multiplied from the right with $A^{-1}$, which is not only dimensionally impossible but also does not give you $(Ax)A^{-1} = x$.2011-09-20
  • 0
    @ThijsLaarhoven: thanks, now corrected. Is the switch at the top to calculate the inverse right?2011-09-20
  • 0
    By the way, as Robert also noted, shouldn't $b$ and $c$ be vectors and $d$ a scalar? I guess the bar over the $x$ and $y$ is to denote they are vectors, but then you should also be consistent and use it for $b$ and $c$ as well. And your solution is now the same as Robert's so that's probably a good thing.2011-09-20
  • 0
    @ThijsLaarhoven: $c^{T}\bar{x}$ is dot-product, returning scalar, so $d$ is scalar. $A\bar{x}$ returns vector, where $A$ is $n \times m$ matrix, and $\bar{x}$ is $m \times 1$ vector -- so $\bar{b}$ must be a $n \times 1$ vector. Added the missing bars over the vectors, now clear?2011-09-20

2 Answers 2

2

This can be seen as a Möbius transformation where the variable is real valued vector instead of a complex scalar.

Define the Möbius transformation as follows: $$ \Delta\star\pmatrix{P&Q\\R &S} = P+Q\Delta(I-S\Delta)^{-1}R $$ for $P,Q,R,S$ matrices over $\mathbb{R}$. (assuming compatible dimensions)

It is just notation don't worry about the commutativity etc. properties. Notice how it coincides with the Wiki link if you assume the matrices and $\Delta$ are scalars. (So you can perform a division)

In your case, the matrix associated with the transformation is $$ y=x\star \left(\begin{array}{c|cc}0 &A &b\\\hline 1 & -c^T&0\end{array} \right) $$ where $$x=\pmatrix{\bar{x}\\1} $$ For the inverse of the transformation to exist, we need the matrix to be invertible. And that can only happen (check the determinant along the first column) if the matrix $\pmatrix{A &b}$ is invertible. Let $V^{-1} := \pmatrix{A&b}$ and also partition $V=\pmatrix{V_1\\V_2}$ compatible with $\pmatrix{c^T&0}$. Then the big matrix inverse becomes $$ \left(\begin{array}{ccc}0 &A &b\\ 1 & -c^T&0\end{array} \right)^{-1} = \left(\begin{array}{cc}c^TV_1 &1\\ V_1&0\\ V_2 &0\end{array} \right) $$

Please note that the zero blocks are of different sizes now. I have to again partition this matrix by the first column/$m+2$ rows, but it would look horrible so I will just give the general form and you can fill in the rest. The inverse transformation can be computed as, $$ x=y\star\left(\begin{array}{c|c}\bar{p}&Q\\\hline r &\bar{s}^T\end{array} \right) = \bar{p} + Qy(1-\bar{s}^Ty)^{-1}r $$

Long story short you have to compute the inverse of the matrix that is associated with the Möbius transformation. Therefore, you need assumptions that prevent the degenerate cases.

3

I don't like the notation $\bar{y}^{-1}$. If $f(x) = \dfrac{A x + b}{c^T x + d} = y$ (where $A$ is an $n \times n$ matrix, $x$, $y$, $b$ and $c$ are $n$-vectors, $d$ is a scalar, and $c^T x + d \ne 0$), then $A x + b = (c^T x + d) y$ so $(A - y c^T) x = d y - b$. Thus if $A - y c^T$ is invertible, $$ x = f^{-1}(y) = (A - y c^T)^{-1} (d y - b)$$

  • 0
    $A$ is $n \times n$ matrix if $m=n$. $A$ is $n \times m$ matrix where $n, m \in \mathbb R_{+}$. The only restriction is the convexity and affinity, noted at the very bottom.2011-09-20
  • 1
    If the matrix is not square, you could try using $x = (A^TA)^{-1}(A^TA)x = (A^TA)^{-1}A^T(Ax) = (A^TA)^{-1}A^Tb$ to go from an equation of the form $Ax = b$ to $x = (A^TA)^{-1}A^Tb$.2011-09-20
  • 0
    yes the notation is bad with $\bar{y}^{-1}$ because $\bar{y}$ is a vector and you cannot take an inverse of a vector, +1. It is inverse of the function $\bar{y}$. Am I clear now? Let $\bar{y} = f(x)$ so $f^{-1}(x)$ is the inverse, certainly less confusing.2011-09-20
  • 0
    @ThijsLaarhoven: let $\bar{k} := \bar{b} - \bar{y}d$ and $H := \bar{y} \bar{c}^{T} - A$. So $f^{-1} = (H^{T}H)^{-1} H^{T} \bar{k}$. How can you know now whether $f^{-1}$ even exists?2011-09-20
  • 1
    If $A$ is $n \times m$ with $n < m$, solutions to $Ax=b$, if they exist, will never be unique. If $n > m$, solutions to $Ax=b$ will not exist for most $b$. But if $A$ has rank $m$, $A^T A$ will be invertible and Thijs's solution gives the solution to $Ax=b$ when it exists. You might look up "Moore-Penrose pseudoinverse".2011-09-21