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
    @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)$

  • 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