When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

McDic's blog

By McDic, history, 4 years ago, In English

Introduction

Hello. I would like to share some nice stuff, called Sherman-Morrison formula. If you know this formula, it's easier to understand how BFGS update works in convex optimization and machine learning. But in this topic, we will just simply focus on this formula and learn how to calculate inverse matrix of rank-$$$1$$$ updated invertible matrix faster.

The motivation of this post is that my problem using Sherman Morrison formula is rejected by multiple coordinators.

Definition

You have invertible $$$\mathbb{R}^{n \times n}$$$ matrix $$$A$$$, and $$$\mathbb{R}^{n}$$$ vectors $$$u$$$ and $$$v$$$. Then $$$ (A + uv^{T})^{-1} = A^{-1} - \frac{A^{-1}uv^{T}A^{-1}}{v^{T}A^{-1}u + 1}$$$. If $$$v^{T}A^{-1}u = -1$$$, then $$$A + uv^{T}$$$ is non-invertible.

Time complexity

You can calculate Sherman Morrison formula in $$$O(n^2)$$$, because $$$A^{-1}u$$$, $$$v^{T}A^{-1}$$$ are vector.

Normally you need $$$O(n^3)$$$ time complexity to calculate inverse matrix except for some special matrix(diagonal matrix etc). But, since you can calculate Sherman-Morrison formula in $$$O(n^2)$$$, if you find some matrix can be represented as rank-$$$1$$$ updated matrix of special matrix, you can calculate inverse of that matrix in $$$O(n^2)$$$.

Generalization

There is a generalization of this formula called Woodbury Matrix Identity.

Sample problem

This problem is that rejected problem.

You have matrix $$$A = \begin{bmatrix} 1 & 2 & \cdots & n \\ n+1 & n+2 & \cdots & 2n \\ \cdots & \cdots & \cdots & \cdots \\ n^{2}-n+1 & n^{2}-n+2 & \cdots & n^{2} \end{bmatrix} + diag(c_{1}, c_{2}, \ldots, c_{n})$$$.

In $$$i$$$-th query, you will select any row or column of $$$A$$$ and multiply this by $$$x_{i}$$$. Compute $$$A^{-1}$$$ if $$$A$$$ is invertible after each query.

Constraints: $$$2 \le n \le 200$$$, $$$1 \le q \le 200$$$, $$$0 \lt c_{i}$$$, $$$x_{i} \neq 0$$$.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

McDic orz. After reading this i feel x2 smarter!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    You have higher rating than me smh

»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

lol, I just realized I should multiply part of $$$A$$$ (first element of $$$A$$$'s formula, or etc) instead of whole $$$A$$$ because this is just multiplying elementary matrix.

»
4 years ago, # |
  Vote: I like it +214 Vote: I do not like it

This is not a tutorial. You just wrote the formula and didn't prove why it works or explain how to come up it. You might as well just post wikipedia link and nothing else. Then at least people wouldn't waste time reading your blog. And I'm very glad that coordinators rejected your "problem". It just asks to apply the formula and doesn't require any thinking. Problem F from 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest is an okay problem which can be solved with this formula and much better than yours.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -193 Vote: I do not like it

    Thanks for wasting additional time to write this comment.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    McDic never claimed it's a tutorial. The beginning of the article says he'd like to share some nice stuff and formula itself seems a nice stuff to me. And thanks to this article we also know that it may be applied to the problem you mentioned, so I think the article is nice.