misc

misc-00

$$$
% From AsciiMath
\newcommand{\bb}[0]{\mathbf}
\newcommand{\bbb}[0]{\mathbb}
\newcommand{\cc}[0]{\mathcal}
\newcommand{\RR}[0]{\bbb{R}}
\newcommand{\CC}[0]{\bbb{C}}
\newcommand{\ZZ}[0]{\bbb{Z}}
\newcommand{\xx}[0]{\times}
\newcommand{\del}[0]{\partial}
% Quick begin/end
\newcommand{\Ba}[0]{\begin{aligned}}
\newcommand{\Ea}[0]{\end{aligned}}
\newcommand{\Bc}[0]{\begin{cases}}
\newcommand{\Ec}[0]{\end{cases}}
\newcommand{\Bm}[0]{\begin{matrix}}
\newcommand{\Em}[0]{\end{matrix}}
\newcommand{\Bmp}[0]{\begin{pmatrix}} % round bracket
\newcommand{\Emp}[0]{\end{pmatrix}}
% Others
\newcommand{\t}[0]{\text}
\newcommand{\l}[0]{\left}
\renewcommand{\r}[0]{\right}
\newcommand{\iprod}[2]{\left<#1,#2\right>}
$$$

## Mobius function

***Notation***

- $\ZZ_n = {0, 1, .., n-1}$: cyclic group of order n,
- $\ZZ^*_n = \{ x \mid \t{gcd}(x, n) = 1 \} \subset \ZZ_n$:
    units of $\ZZ_n$ (multicative group),
- For the special case of $n = 1$, we treat $\ZZ^*_1 = \ZZ_1 = \{ 0\}$.

### Def. 1

$$
\mu(n) \equiv
  \Bc
    0          & (\t{if}~~ \exists i.~ e_i >= 2)
                        ~~(\t{i.e.}~n: {\t{not square free}}), \\
    (-1)^{|I|} & (\t{otherwise}). \\
  \Ec
$$

where $n$ has prime factorization $n = \prod_{i \in I} p_i^{e_i}$.

***N.B.***

- It's easy to see $\mu$ is multiplicative.


### Def. 2

$$
\Ba
\t{SR}(n) &\equiv \sum_{k \in \ZZ_n} \exp(i 2 \pi k/n), \\
\t{SP}(n) &\equiv \sum_{k \in \ZZ^*_n} \exp(i 2 \pi k/n).
\Ea
$$

***N.B.***

- For the special case of $n = 1$, we have $\t{SP}(1) = \t{SR}(1) = \exp(0) = 1$.


### Prop. 3

$$
\ZZ_n = \bigcup_{d | n} \frac{n}{d}\cdot\ZZ^*_d \\
$$

and the sets under the union are disjoint each other.

**N.B.**

- $x \cdot S$ means that $x \cdot S \equiv \{ xy \mid y \in S \}$.
- This implies that $\sum_{d | n} \phi(d) = n$ where $\phi$: Euler's totient.

***Proof***

TODO

### Prop. 4

$$
\t{SR}(n) = \sum_{d | n} \t{SP}(d).
$$

***Proof***

$$
\Ba
\sum_{d | n} \t{SP}(d)
  &= \sum_{d | n} \sum_{k \in \ZZ^*_d} \exp(i 2 \pi k/d) \\
  &= \sum_{d | n} \sum_{k \in \ZZ^*_d} \exp\l(i 2 \pi (\frac{n}{d}k)/n\r) \\
  &= \sum_{d | n} \sum_{k' \in \frac{n}{d}\ZZ^*_d} \exp\l(i 2 \pi k'/n\r) \\  
  &= \sum_{k' \in \ZZ_n} \exp\l(i 2 \pi k'/n\r)
    ~~(\because \t{Prop. 3}) \\
  &= \t{SR}(n).
\Ea
$$

### Prop. 5

$\t{SP}(n)$ is multiplicative, i.e.

$$
\gcd(n, m) = 1 \implies \t{SP}(nm) = \t{SP}(n) \t{SP}(m).
$$

***Proof***

Given $\gcd(n, m) = 1$, we have,

$$
\Ba
\t{SP}(n) \t{SP}(m)
  &= \sum_{k \in \ZZ^*_{n}} \exp(i 2 \pi k / n)
      \sum_{l \in \ZZ^*_{m}} \exp(i 2 \pi l / m) \\
  &= \sum_{(k, l) \in \ZZ^*_{n} \xx \ZZ^*_{m}}
      \exp(i 2 \pi (k / n + l / m)) \\
  &= \sum_{(k, l) \in \ZZ^*_{n} \xx \ZZ^*_{m}}
      \exp(i 2 \pi (km + ln) / (n m)).
\Ea
$$

Thus, it suffices to show $f(l, m) \equiv k m + l n: \ZZ^*_{n} \xx \ZZ^*_{m} \to \ZZ^*_{nm}$
is well-defined and bijective.

For that, we show $\gcd(k m + l n, nm) = 1$ and $f$: injective.
(NOTE: the rest is easy...)


### Prop. 6

$$
\t{SR}(n) =
  \Bc
    1 & (\t{if}~ n = 1) \\
    0 & (\t{otherwise}).
  \Ec
$$

***Proof***

Writing $\alpha = 2 \pi / n$, we have,

$$
\Ba
(\exp(i 2 \pi / n) - 1) \t{SR}(n)
  &= \sum_{k : 1...n} \exp(i 2 \pi k / n) - \sum_{k : 0...n-1} \exp(i 2 \pi k / n) \\
  &= \exp(i 2 \pi n / n) - \exp(i \alpha 0 / n) \\
  &= 0.
\Ea
$$

### Prop. 7

For $p$: prime, 

- $\t{SP}(p) = -1$.
- $\t{SP}(p^e) = 0$ where $e >= 2$.


***Proof***

From Prop. 4 and Prop. 6, we have:

$$
0 = \t{SR}(p^e) = \t{SP}(1) + \t{SP}(p) + ... +  \t{SP}(p^e).
$$

Thus, for $e = 1$, we have $\t{SP}(p) = - \t{SP}(1) = -1$.

For $e >= 2$, by induction, we have $\t{SP}(p^e) = 0$.


### Prop. 8

$$
\mu(n) = \t{SP}(n).
$$

***Proof***

This follows from multiplicativity and the coinciding base case $\mu(p^e) = \t{SP}(p^e)$.


### Prop. 9 (Mobius inversion formula)

$$
g(n) = \sum_{d | n} f(d)
  \implies
    f(n) = \sum_{d | n} \mu(d) g(\frac{n}{d}).
$$

***Proof***

$$
\Ba
\sum_{d | n} \mu(d) g(\frac{n}{d})
  &= \sum_{d | n } \mu(d) \sum_{e | \frac{n}{d}} f(e) \\
  &= \sum_{d | n ~\wedge~ d e | n} \mu(d) f(e) \\
  &= \sum_{e | n} f(e) \sum_{d | \frac{n}{e}} \mu(d) \\  
  &= \sum_{e | n} f(e) ~ \delta(n/e, 1)
    ~~(\because \t{Prop. 4, 6, 8}) \\
  &= \sum_{e | n} f(e) ~ \delta(e, n) \\
  &= f(n).
\Ea
$$


## Slerp (Spherical linear interpolation)

***Notation***

- $p_0, p_1 \in \RR^{n}$,

- $|p_0| = |p_1| = 1$,

- $\iprod{p_0}{p_1} = \cos(\theta)$,

- $\sin(\theta) \neq 0$ i.e. $p_0$ and $p_1$ are not parallel.


### Def. 1

$$
p(t)
  \equiv
    \frac{1}{\sin(\theta)}
      (
        \sin((1 - t) \theta)p_0 +
        \sin(t \theta)p_1
      ).
$$

**N.B.**

- Clearly $p(0) = p_0$ and $p(1) = p_1$.
- By writing $a \equiv (1 - t) \theta$ and $b \equiv t \theta$, we have:

  $$
    p(t) \equiv
      \frac{\sin(a) p_0 + \sin(b) p_1}{\sin(a + b)}.
  $$
  
- $
\del_t p(t)
  =
    \dfrac{\theta}{\sin(\theta)}
      (- \cos((1 - t) \theta) p_0 + \cos(t \theta) p_1)
  =
    \theta
      \dfrac{- \cos(a) p_0 + \cos(b) p_1 }{\sin(a + b)}.
$

- $
\del_t^2 p(t)
  =
    \dfrac{- \theta^2}{\sin(\theta)}
      (\sin((1 - t) \theta) p_0 + \sin(t \theta) p_1)
  =
    - \theta^2 p(t).
$

### Prop. 1

$$
\iprod{p_0}{p(t)} = \cos(t \theta).
$$

***Proof***

Using $a, b$, we can write:

$$
\Ba
\iprod{p_0}{p(t)}
  &= \frac{1}{\sin(a + b)}
      (\sin(a) |p_0|^2 + \sin(b) \iprod{p_0}{p_1}) \\
  &= \frac{\sin(a) + \sin(b) \cos(a + b)}{\sin(a + b)}.
\\
\cos(t \theta)
  &= \cos(b).
\Ea
$$

Thus, we see:

$$
\Ba
\iprod{p_0}{p(t)} = \cos(t \theta) 
  &\iff
    \sin(a) + \sin(b) \cos(a + b) = 
    \sin(a + b) \cos(b) \\
  &\iff
    \cos(a + b) \sin(b) - \cos(a + b) \sin(b) =  \sin(a).
\Ea
$$

### Prop. 2

$$
|p(t)| = 1.
$$

***Proof***

Noting that $\del_t |p(t)|^2 = 2 \iprod{p(t)}{\del_t p(t)}$ and $|p(0)| = |p_0| = 1$,
it suffices to show that $\iprod{p(t)}{\del_t p(t)} = 0$. Indeed, we see

$$
\Ba
\iprod{p(t)}{\del_t p(t)}
  &= 
    \frac{\theta}{\sin(a + b)^2}
      \iprod{\sin(a) p_0 + \sin(b) p_1}{-\cos(a) p_0 + \cos(b) p_1} \\
\Ea
$$

Expanding the last term:

$$
\Ba
&\iprod{\sin(a) p_0 + \sin(b) p_1}{- \cos(a) p_0 + \cos(b) p_1} \\
  &=
    - \sin(a) \cos(a) + \sin(b) \cos(b)
    + (\sin(a) \cos(b) - \cos(a) \sin(b)) \cos(a + b) \\
  &=
    \frac{1}{2} \l(- \sin(2a) + \sin(2b) \r)
    + \sin(a - b) \cos(a + b) \\
  &=
    \frac{1}{2} \l(- \sin((a + b) + (a - b)) + \sin((a + b) - (a - b)) \r)
    + \sin(a - b) \cos(a + b) \\
  &= 0.
\Ea
$$


### Prop. 3

$$
|\del_t p(t)| = |\theta|.
$$

***Proof***

We have $|\del_t p(t)|$: constant since:

$$
\del_t |\del_t p(t)|^2
  = 2 \iprod{\del_t p(t)}{ \del_t^2 p(t) }
  = - 2 \theta^2 \iprod{\del_t p(t)}{p(t)} = 0.
$$

Thus, it suffices to show $|\del_t p(0)| = |\theta|$. Indeed, we have:

$$
|\del_t p(0)|
  = |\theta|
      \l| \frac{- \cos(\theta) ~ p_0 + p_1}{\sin(\theta)} \r| = 0.
$$

The last equation follows from:

$$
|- \cos(\theta) ~ p_0 + p_1|^2
  = \cos^2(\theta) + 1 - 2 \cos(\theta) \iprod{p_0}{p_1}
  = 1 - \cos^2(\theta) = \sin^2(\theta).
$$


## Conjugate gradient descent

***Notation***

- $A \in \RR^{n \xx n}$: positive definite
- $x, b \in \RR^n$


### Def. 1

- $x_0 \equiv x$,
- $r_0 \equiv A x_0 - b$,
- $p_0 \equiv r_0$,
- $x_{n + 1} \equiv x_n + \alpha_n p_n$,
- $r_{n + 1} \equiv A x_{n + 1} - b = (A x_n - b) + \alpha_n A p_n = r_n + \alpha_n A p_n$,
- $p_{n + 1} \equiv r_{n + 1} + \beta_n p_n$,

where

- $\alpha_n \equiv - \dfrac{\iprod{p_n}{r_n}}{\iprod{p_n}{A p_n}}$,

- $\beta_n \equiv - \dfrac{\iprod{r_{n+1}}{A p_n}}{\iprod{p_n}{A p_n}}$,

running until we find $r_n = 0$.

**N.B.**

- Writing $f(x) \equiv \dfrac{1}{2} \iprod{x}{A x} - \iprod{x}{b}$,
  we have $\del_x f(x) = A x - b$.
  
- $\del_\alpha f(x + \alpha p)
    = \iprod{\del_x f(x + \alpha p)}{p}
    = \iprod{A(x + \alpha p) - b}{p}$.
  
- $\alpha_n$ is taken so that
  $\iprod{r_{n + 1}}{p_n} = \del_{\alpha_n} f(x_n + \alpha_n p_n) = 0$
  (i.e. line-search minimum).
  
- $\beta_n$ is taken so that $\iprod{p_{n + 1}}{A p_n} = 0$.

- $|p_{n + 1}|^2 = |r_{n + 1}|^2 + |p_n|^2$ thus
  $r_{n + 1} \ne 0 \implies p_{n + 1} \ne 0$.
  
  Therefore, $\alpha_n$ and $\beta_n$ are well-defined as long as $r_n \ne 0$.
  
- Furthermore
  $\iprod{p_n}{r_n} = \iprod{r_n + \beta_{n - 1} p_{n - 1}}{r_n} = \iprod{r_n}{r_n}$,
  thus $r_n \ne 0 \implies \alpha_n \ne 0$.


### Prop. 2

- $\iprod{p_i}{A p_j} = \iprod{r_i}{r_j} = 0$ for $i \ne j$.

***Proof***

Prove by induction.

We show $\iprod{r_{n + 1}}{r_k} = 0$:

$$
\Ba
\iprod{r_{n + 1}}{r_n}
  &= \iprod{r_{n + 1}}{p_n - \beta p_{n - 1}} \\
  &= - \beta \iprod{r_{n + 1}}{p_{n - 1}} \\
  &= - \beta \iprod{r_n + \alpha A p_n}{p_{n - 1}} \\
  &= - \alpha \beta \iprod{A p_n}{p_{n - 1}} \\
  &= 0 ~~(\because \t{IH}), \\
\Ea
$$

and for $k < n$,

$$
\Ba
\iprod{r_{n + 1}}{r_k}
  &= \iprod{r_n + \alpha A p_n}{r_k} \\
  &= \alpha \iprod{A p_n}{r_k} ~~(\because \t{IH}) \\
  &= \alpha \iprod{A p_n}{p_k - \beta p_{k - 1}} \\
  &= 0 ~~(\because \t{IH}).
\Ea
$$

Next, we show $\iprod{p_{n + 1}}{A p_k} = 0$.

For $k = n$, it was shown above and for $k \lt n$,

$$
\Ba
\iprod{p_{n + 1}}{A p_k}
  &= \iprod{r_{n + 1} + \beta p_n}{A p_k} \\
  &= \iprod{r_{n + 1}}{A p_k} ~~(\because \t{IH})\\  
  &= \iprod{r_{n + 1}}{\frac{r_{k + 1} - r_k}{\alpha}} \\
  &= 0 ~~(\because \t{IH}).
\Ea
$$


### Prop. 3

- $\alpha_n
    \equiv - \dfrac{\iprod{p_n}{r_n}}{\iprod{p_n}{A p_n}}
    = - \dfrac{\iprod{r_n}{r_n}}{\iprod{p_n}{A p_n}}$,

- $\beta_n
    \equiv - \dfrac{\iprod{p_n}{A r_{n+1}}}{\iprod{p_n}{A p_n}}
    = \dfrac{\iprod{r_{n+1}}{r_{n+1}}}{\iprod{r_n}{r_n}}$.

***Proof***

Noting that

- $r_{n + 1} = r_n + \alpha_{n} p_n$,
- $p_n = r_n + \beta_{n - 1} p_{n - 1}$,
- $\iprod{r_n}{p_{n - 1}} = \iprod{r_{n + 1}}{p_n} = 0$,
- $\iprod{r_{n + 1}}{r_n} = 0$,
- $\iprod{p_{n - 1}}{A p_n} = 0$,

we see:

- $\iprod{r_n}{p_n} = \iprod{r_n}{r_n + \beta_{n - 1} p_{n - 1}} = \iprod{r_n}{r_n}$,

- $\iprod{r_{n + 1}}{A p_n}
    = \iprod{r_{n + 1}}{\dfrac{r_{n + 1} - r_n}{\alpha_n}}
    = \dfrac{\iprod{r_{n + 1}}{r_{n + 1}}}{\alpha_n}$,
    
- $\iprod{p_n}{A p_n}
    = \iprod{p_n}{\dfrac{r_{n + 1} - r_n}{\alpha_n}}
    = - \dfrac{\iprod{p_n}{r_n}}{\alpha_n}
    = - \dfrac{\iprod{r_n}{r_n}}{\alpha_n}$.

---

## Singular value decomposition


### Prop. 1 (Polar decomposition)

- $A \in \CC^{n \xx n}$: invertible,
- $A^\dagger A$: positive definite,
- $P \equiv (A^\dagger A)^{1/2}$: positive definite,
- $U \equiv A \l((A^\dagger A)^{1/2}\r)^{-1}$: unitary,
- $A = U P$: polar decomposition.

### Prop. 2 (Existence of SVD)

Given,

- $A \in \CC^{n \xx m}$,

There exist $U \in \CC^{n \xx n}, V \in \CC^{m \xx m}$ : unitary
and $D \in \RR_{\ge 0}^{n \xx m}$ : diagonal s.t.

$$
A = U D V^\dagger.
$$

***Proof***

- Quick proof for the special case of $A \in \CC^{n \xx n}$: invertible.

    - By polar decomposition, $A = U P$.
    - By spectral decomposition, $P = V D V^\dagger$.
    - Thus, $A = (U V) D V^\dagger$.

- Proof for general case (i.e. non-square or non-invertible).

By spectral decomposition, $A^\dagger A = P W P^\dagger \in \CC^{m \xx m}$ where
$P$ is unitary and $W$ is non-negative diagonal.

Next, we find permutation $S \in \CC^{m \xx m}$ s.t. $A P S$ has
column vectors with decreasing norm (i.e. sorting columns of $A P$ by their norm).

Next, by QR decomposition $A P S = Q R$
where $Q \in \CC^{n \xx n}$ and $R \in \CC^{n \xx m}$.

Here notice that $R$ has decreasing norm column vectors since $Q$ is unitary.
Also, we note:

$$
R^\dagger R
  = (Q^\dagger A P S)^\dagger Q^\dagger A P S
  = S^\dagger P^\dagger A^\dagger Q Q^\dagger A P S
  = S^\dagger W S: \t{diagonal}.
$$

Finally, by **Lemma. 3** below, we know $R$ is actually diagonal and
thus $A = Q R (P S)^\dagger$ is singular value decomposition.


### Lemma. 3

Given,

- $R$: upper triangle with column vectors of decreasing norm
- $R^T R$: diagonal

Then, $R$: diagonal.

***Proof***

First, we write:

$$
R =
  \Bmp
    X & Y \\
    0 & Z
  \Emp
$$

where $X$: invertible and $Z_{1, 1} = 0$,.

Then,

$$
R^T R =
  \Bmp
    X^T X & X^T Y \\
    Y^T X & Y^T Y + Z^T Z.
  \Emp  
$$

Since $X$: invertible and $R^T R$: diagonal, we find 

- $Y = 0$,
- $X^T X$: diagonal, thus $X^T$: upper triangle, thus $X$: diagonal
- $
R =
  \Bmp
    X & 0 \\
    0 & Z
  \Emp
$ and $Z_{1, 1} = 0$ thus $Z = 0$ since decreasing norm.


### Prop. 4 (Orthogonal Procrustes problem)

Define

- $\iprod{A}{B} \equiv \t{tr}(A^T B)$,
- $|A| = \sqrt{\iprod{A}{A}}$.

Given

- $A, B \in \RR^{n \xx m}$,
- $B A^T = U D V^T \in \RR^{n \xx n}$:
  singular value decomposition with $D$ decreasing diagonal,

$$
\min\limits_{P : \t{SO}(3)}|A - P B|.
$$


$$
\Ba
|A - P B|^2
  &= \iprod{A - P B}{A - P B} \\
  &= |A|^2 + |P B|^2 - 2 \iprod{A}{P B} \\
  &= |A|^2 + |B|^2 - 2 \iprod{A}{P B} \\
\iprod{A}{P B}
  &= \t{tr}(A^T P B)
  = \t{tr}(P B A^T)
  = \t{tr}(P U D V^T) \\
  &= \t{tr}((V^T P U) D).
\Ea
$$

By taking
$$
P =
  V 
  \Bmp
    I & 0 \\
    0 & \t{det}(V U^T)
  \Emp
  U^T,
$$
we have $\iprod{A}{PB} = (\sum_{i < n} D_{i, i}) + \t{det}(V U^T) D_{n, n}$.