3
$\begingroup$

The function is given by $f(X) = (AX^{-1}A^\top + B)^{-1}$ where $X$, $A$, and $B$ are $n \times n$ positive definite matrices.

I'm trying to find the Lipschitz constant such that $\| f(X)-f(Y) \| \leq L \|X-Y\|$ where $X \geq 0$ and $Y \geq 0$. Motivated by Lemma 3.1 in Nonlinear Systems(H. Khalil, 3rd Ed.), I tried to find the derivative of $f(X)$ (i.e. $\| \frac{ \partial f(X)}{\partial X} \|$) but it's not easy to find the derivative of a function of a matrix over a matrix.

How can I find the Lipschitz constant? or Please let me know if there exists the way to calculate the derivative of a function of a matrix.

$\endgroup$
  • 1
    $\begingroup$ I understand that $A$ (and then the others matrices as well) is not assumed to be symmetric. Then what do you mean here by "$A$ is positive definite matrix" (and $X\ge0$) ? Is it $v^\top A v >0$ for nonzero vectors $v$? Or $A$ has positive real eigenvalues? $\endgroup$ – Pietro Majer Jun 18 at 11:52
  • 1
    $\begingroup$ it's not easy to find the derivative of a function of a matrix over a matrix Actually it's quite easy. All you need here is the formula $(X+H)^{-1} = X^{-1} - X^{-1}HX^{-1} + O(\|H\|^2)$, which follows from the Neumann series. Applying it twice you should get your derivative. $\endgroup$ – Federico Poloni Jun 18 at 13:15
2
$\begingroup$

I assume $X\ge0$ means $u^\top X u\ge0$, and that $B$ is definite positive $$\inf_{\|u\|=1} u^\top B\, u:=\beta>0.$$ I also assume matrix norms are the Euclidean operator norms.

Compute the differential by the chain rule, as suggested in comments by F.Poloni: $$Df(X)H=(AX^{-1}A^{\top}+B)^{-1}AX^{-1}\cdot H\cdot X^{-1}A^{\top}(AX^{-1}A^{\top}+B)^{-1}$$ $$=(A^{\top}+XA^{-1}B)^{-1}\cdot H \cdot(A+BA^{-\top}X)^{-1}=$$ $$=\big(B^\top+Y\big)^{-1}B^\top A^{-\top}\cdot H\cdot A^{-1}B^\top\big(B^\top+Z)^{-1}, $$

where $Y:=B^{\top}A^{-\top} X A^{-1}B\ge0 $ and $Z:=BA^{-\top}XA^{-1}B^\top\ge0$, conjugated to $X\ge0$. Thus for any unit norm vector $u\in\mathbb{R}^n $ $$\big\|\big(B^\top+Y\big)u\big\|\ge u^\top\big(B^\top+Y\big)u\ge u^\top B u \ge\beta$$ and $$\big\|\big(B^\top+Z)u\big\|\ge u^\top\big(B^\top+Z)u \ge u^\top B u \ge\beta.$$ Hence $$\big\|\big(B^\top+Y\big)^{-1}\big\|\le \beta^{-1}$$ and $$\big\|\big(B^\top+Z)^{-1}\big\|\le \beta^{-1}.$$ Therefore $$\|Df\|_\infty\le\|B\|^2\|A^{-1}\|^2\beta^{-2}$$ which is also a Lipschitz constant for $f$, since its domain is convex, $\{X\ge0\}$.

$$*$$

Rmk. The above bounds on the $L_2$ operator norms (or others matrix norms) could be improved, but not up to $$\big\|\big(A^{\top}+XA^{-1}B\big)^{-1}\big\|\le\big\|A^{-1}\big\|,$$ even for symmetric definite positive matrices. Take e.g. $n=2$ and $$A=:I=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\quad X:=\begin{bmatrix} 5/2 & 1 \\ 1 & 1/2 \end{bmatrix}\quad B:=\begin{bmatrix} 1 & -1/2 \\ -1/2 & 1/2 \end{bmatrix}$$

Then $$\big(A^{\top}+XA^{-1}B\big)^{-1}=\big(I+XB\big)^{-1}= \begin{bmatrix} 4/15 & 4/15\\ -4/15 & 16/15 \end{bmatrix}$$ whose maximum singular value is $\displaystyle{2\over 15}\sqrt{29}+{2\over 5}>1=\|A^{-1}\|$. The same holds for the Frobenius, and other common entry-wise norms (due to the coefficient $16/15>1$).

$\endgroup$
2
$\begingroup$

Let $h=Y-X$. Using the first order expansion of the matrix inverse, $$ f(X+h)=(A(X^{-1}-X^{-1}hX^{-1})A^\top+B)^{-1}+O(\|h\|^2) $$ Now let $Z=AX^{-1}A^\top+B$ and let $g = AX^{-1}hX^{-1}A^\top$. Then $$ f(X+h)=(Z-g)^{-1}+O(\|h\|^2)=Z^{-1}+Z^{-1}gZ^{-1}+O(\|h\|^2). $$ Since $Z^{-1}=f(X)$, it follows that $$ f(X+h)-f(X)=Z^{-1}AX^{-1}hX^{-1}A^\top Z^{-1}+O(\|h\|^2). $$ Using $Z^{-1}AX^{-1}=(XA^{-1}Z)^{-1}=(A^T+XA^{-1}B)^{-1}$, we obtain that $$ \|Z^{-1}AX^{-1}\|\leq \|A^{-1}\|. $$ Similarly, $\|X^{-1}A^\top Z^{-1}\|\leq \|A^{-1}\|$. Consequently, $$ \|f(X+h)-f(X)\|\leq \|A^{-1}\|^2\|h\|+O(\|h\|^2), $$ yielding a Lipschitz constant of $L=\|A^{-1}\|^2$.

$\endgroup$
  • 1
    $\begingroup$ Yet it is not clear why $\|Z^{-1}AX^{-1}\|\le\|A^{-1}\|$(here I had to introduce a factor); could you explain it? $\endgroup$ – Pietro Majer Jun 19 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.