Sunday 16 June 2024

Use of geometric sum as inverse in function spaces

When I teach first year linear algebra, one of the main show is the use of diagonalization to simplify matrix computation then to link that with various applications. This is the real point where you feel the real use of these concepts other than making up its geometric meaning. Cayley-Hamilton, characteristic polynomial for recurrence sequences, Markov chain and so on.

To start with, consider a matrix $A$. If $\sum A^k = I + A + A^2 + \ldots $ is well-defined (aka converges) then by geometric series we know it is equal to $(I-A)^{-1}$. If we do the other way round we can compute the geometric series of $I-A$, we will recover the inverse $(I-(I-A))^{-1} = A^{-1}$. The problem is...does the geometric sum converges? This is where the eigenvalues kick in.

For diagonal matrix $D$, $\sum D^k$ converges iff all diagonal entries (aka eigenvalues) are of norm less than or equal 1. If $A$ is diagonalizable we can write $A = PDP^{-1}$, then $(I-A) = P(I-D)P^{-1}$, so we want the diagonal entries of $(I-D)$ to be in $(-1,1)$. Or rather, we want all eigenvalues of $A$ to be in $(0,2)$. But this is a very limited result. Can we do better? Yes!

Notice that we can tweek the eigenvalues by multiplying a constant. Let $c \in \mathbb{R}$ be non-zero so that all eigenvalues of $A/c$ to be in $(0,2)$, then the same procedure may proceed. 

Consider the matrix $A = \begin{bmatrix}5&4\\2&3\end{bmatrix}$ with eigenvalues 1 and 7, we take $c = 8$. Write $A = PDP^{-1}$ then $I - D/c$ has diagonal entries 7/8 and 1/8. Geometric sum gives $\sum (I-D/c)^k = \begin{bmatrix}8&0\\0&8/7\end{bmatrix}$. 

Plugging back we have $P(\sum (I-D/c)^k)P^{-1} = \frac{8}{7}\begin{bmatrix}3&-4\\-2&5\end{bmatrix}$, which is precisely $cA^{-1}$. Don't forget that $(A/c)^{-1} =cA^{-1}\neq A^{-1}/c$!

*

Now let us forget about linear algebra and just the a step forward. How about using geometric sum in function spaces? 

We start with a very vague idea. Let $M$ be the integral operator, then we obviously obtain $(I-M)[\exp] = -C$ where $C$ arises from the integral. What if $(I-M)$ has inverse $(I+M+M^2+...)$? Let's say $M[-C] = -Cx + C_1$, then $M^2[-C] = -Cx^2/2 + C_1x + C_2$, and so on. One obtains $(\sum M^k)[-C] = (-C+\sum C_i)(1 + x + x^2/2 + \ldots)$, and checking $x = 0$ gives $-C + \sum C_i = 1$. This is such a lucid dream because we just proved the series $e^x = \sum x^k/k!$ without differentiation at all!!

But wait, there are too many technical problems in the above argument to the point if I read that from my student's assignment I would have torn that paper into pieces. The gaps are not fatal, but we have to be very, very careful.

The biggest problem of all, is that integral operator in that arbitrary form, is likely unbounded. We must sacrifice our dream of working over the reals and work in $[0,N]$ instead. Since $N$ is arbitrary we can extend that basically to the reals, at least pointwisely.

In a bounded interval $L^p$ spaces work similarly but the best is $L^{\infty}$ because we immediately give the norm of the integral operator. Define $M_0:L^{\infty}([0,N]) \to L^{\infty}([0,N])$ by $M_0f(x) = \int ^x_0f(u)du$. This is well defined because $M_0f(x) \leq N\|f\|_{\infty}$, and it also implies that $\|M_0\| = N$ (the equality is obvious by taking $f = 1$). 

We solved unboundedness but we need $\| M_0 \|<1$ for that to work. What should we do now? Well, just copy what we did to matrices. Define $M = M_0/(N+1)$ and try again: $M[e^x] = (e^x-1)/(N+1)$ but $I[e^x] = e^x$...they don't add up. It turns out that tweeking $M$ won't suffice because a tweek to the function is necessary as well. 

Let $f = e^{x/(N+1)}$, then $Mf = (e^{x/(N+1)} - 1)$ and so $(I-M)f = 1$. Since $\|M\| < 1$, $\sum M^k$ is a well-defined operator and is the inverse of $(I-M)$. Therefore $f = (\sum M^k)[1]$. Induction gives $M^k[1](x) = (x/(N+1))^k/k!$, so $e^{x/(N+1)} = \sum (x/(N+1))^k/k!$ uniformly in $[0,N]$. A substitution recovers the desired series for $e^x$.

Many would think the job is done here but this is a false sense of security. Not an easy gap to spot -- including me when I first drafted. We established the equality in $L^{\infty}$ or uniformly, but in the pointwise sense this is only almost everywhere. The good news is we do not have to worry about the trap of generating the series using the series anymore so many more tools are now available like continuity. Since both the exponential function and the series are continuous everywhere, the two expressions are indeed equal everywhere.

*

I believe this is the first time I write about functional analysis here but this is actually my expertise. These are absolutely not what one would encounter in research, but very fun to share across all levels of undergraduate students.

The idea of $\sum A^k = (1-A)^{-1}$ is the cornerstone of spectral theory because when we look at the spectrum we want to see the set where $A-\lambda I$ is invertible, or equivalently where $I - A/\lambda$ is invertible. The fact that geometric series converges says that when $A$ is small enough to $I$ then $(I-A)$ is always invertible which gives us lots of information about the spectrum.

Of course, knowing that $(I-A)$ is invertible for small $A$ says nothing about any other operators in the space. In particular, it says nothing about invertibility of operators that fails the condition for geometric sum.

This is particularly clear when we revisit the matrix example. I claim that the above method applies to all diagonalizable matrices where all eigenvalues are of the same sign (and are non-zero) (proof: left to reader). But that left out almost all diagonalizable matrices where eigenvalues contain both signs. Are they not invertible? Absolutely not! The moment they are diagonalizable with non-zero eigenvalues they are straightaway invertible, just that this particular approach doesn't apply.

One problem to the readers: my proof above relies on the fact that $e^0 = 1$. Can you recreate the proof for when $x < 0$? 

We finish with an extra food for thought: one computes $M^4[\sin](x) = \sin x - x + x^3/6$, so $(I-M^4)[\sin](x) = x - x^3/6$. You already see the pattern: $(\sum (M^4)^k)[x - x^3/6]$ is precisely the series for $\sin x$. (Technical problems like convergence and range is easy like above so we left them to readers as well.) Can we do the same for any differential equation solution like functions? Does it depend on the radius of convergence? Or...does it apply to all $C^{\infty}$ functions? How interesting...

Tuesday 11 June 2024

DDR, the 10th year

Another "10th year" among many others that I have already wrote about on my blog, but DDR is different. This is something that I consistently keep track of, and progress is really made over the time. 

Since when did I started playing DDR? A local Osu! player lured me to try so when we were in arcade where I played Taiko (up to 9* and a few 10*s at the 11th gen cab) and jubeat (level 10 in Copious). That was a X3 vs X2 mix cab with a very beginner friendly mode where everything is limited to 1-5 "foot level" (the old foot level was already scrapped).

Like everyone else, I started with failing these easiest levels. But soon I started passing level 8 (I believe) consistently, then level 10 then 12, a year later 14. This arcade closed around the end of 2015 Q3, but this is a story for another day but you would probably have seen mentions of the exact same arcade somewhere else in the blog.

The exact time where I started couldn't be dated precisely, but surely it's well before the second half of 2014 because I had evidence of me playing up to level 13-14 at the time already. In many occasions I wrote the (N-2014)th year in the title but actually it's the (N-2014+1)th year of me playing DDR. 

I ended up settled in new arcades. The first one had an ITG but soon disgustingly replaced that by PIU, so I ordered soft pad and practice with stepmania at home until another arcade opened where I stayed for a long time.

Here are some snapshots:
2016, the 2nd year: doing well at level 14, attempts on MAX300 the gateway to advanced level
2017, the 3rd year: doing well mostly at level 16 and a few 17, almost passed 嘆きの樹 ESP
2018, the 4th year: doing well at level 17 and a few 18, 500 credits since DDR2014 (not accounting X3 and 2013 ver.)
2019, the 5th year(in Chinese): doing well at level 18 except OTP and ENDYMION, able to do 18 set, looking to clear 19
2022, the 8th year: Fully cleared 18, yet unable to clear at level 19

I was possibly the best in 2019 when my stamina was clearly prepared for 19. After covid I became better in terms of single attempts, but never bested the 2019 self in terms of readiness towards level 19. I had a 750k score at Paranoia Revolution CSP but that was it.

It is a bit sad to say that my performance peak in 2019 aligned with my physical peak in terms of age. You clearly feel that more warmup is necessary in 2024 for similar performance than in 2019. That does not imply I am never going to outperform the 2019 self again, but it requires great and consistent effort. In fact I am quite happy with a few scores obtained in the past year. Such score on a shitty 2nd gen cab means I can easily get an A in a proper cab. 

And I am back ready for the challenge.

Reason behind that? Well firstly I am done with Chunithm. Not because the game was poor, but I already had my potential fully exhausted in reaching 16.00. I can probably go slightly higher if I try really, really hard but it is not very meaningful. Chunithm is known for its vast song collection, but after playing the game intensively for a year the collection lost its attraction. Yes SEGA is still adding new songs in mass frequently, but I do not play the game just for the song and DDR is still my top choice.

Another reason is...I finally have my hands on a gold cab that I can play in long term. Not when I travel to Japan where I had to travel between two golden league seasons just for the golden league scores so that I can unlock those course trials. But a gold cab that I can play any day I desired.


I do not see myself getting close to my 2022 let alone 2019 performance for now. It takes time to get used with gold cabs with the lowered pads. When I did course trials in the past that was in survival mode, or travelling mode at the least where I don't try hard for scores. In general practice though that should be something worth minimal care. Gold cab speed is also significantly different: 450BOOST becomes 400BOOST -- at least I know I can only read 350BOOST on 2nd gen cab not because I lost my reading ability. 

My first goal is to resume my practice of 7 credits a session, then clear most 18s. Many new gimmicky/almost 19/plain bullshit level 18 maps had been added these years, and let us see how my plan goes! We will meet again in this record in a year.

For the record before Konami scraps the site again:

X2-2014 + ITG: ~500 plays without hard evidence
A~A20plus: 1993 plays
A3: 226 plays up to 09/06/2024.