User:Zhenlige/RTT notes

注意：本页面为公开的个人笔记，内容可能存在中英夹杂、前后联系不清晰等现象。

Note: This page contains public personal notes, and may show phenomenons like mixing Chinese and English or fuzzy connections between contents.

[math]\displaystyle{ \vec{a} }[/math]：向量vector [math]\displaystyle{ \overleftarrow{a} }[/math]：covector

对偶范数 dual norm

若向量范数[math]\displaystyle{ f(\vec{a}),g(\vec{b}) }[/math]使[math]\displaystyle{ g(\vec{b})=\sup\left\{x\left|x=\frac{\vec{a}\cdot\vec{b}}{f(\vec{a})},\vec{a}\neq\vec{0}\right.\right\} }[/math]且[math]\displaystyle{ f(\vec{a})=\sup\left\{x\left|x=\frac{\vec{a}\cdot\vec{b}}{g(\vec{b})},\vec{b}\neq\vec{0}\right.\right\} }[/math]，则称[math]\displaystyle{ f,g }[/math]为对偶范数。

定理1：[math]\displaystyle{ p }[/math]范数[math]\displaystyle{ \|\vec{a}\|_p=\left(\sum_i|a_i|^p\right)^\frac1p,p\gt 1 }[/math]的对偶范数为[math]\displaystyle{ q }[/math]范数，其中[math]\displaystyle{ q=\frac{p}{p-1} }[/math]。1范数的对偶为∞范数[math]\displaystyle{ \|\vec{a}\|_\infty=\lim_{p\to+\infty}\|\vec{a}\|_p=\max|a_i| }[/math]。

证明：注意到[math]\displaystyle{ (p-1)(q-1)=1 }[/math]。考虑函数[math]\displaystyle{ f_q(\vec{b})=\sum_i|b_i|^q=\|\vec{b}\|_q^q }[/math]，其梯度为[math]\displaystyle{ \nabla f_q(\vec{b})=q\begin{bmatrix}\mathrm{sgn}(b_1)|b_1|^{q-1}&\mathrm{sgn}(b_2)|b_2|^{q-1}&\cdots&\mathrm{sgn}(b_n)|b_n|^{q-1}\end{bmatrix}^\mathrm{T} }[/math]。

对于零向量，原式显然成立。对于任意非零向量[math]\displaystyle{ \vec{a}=\begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix}^\mathrm{T} }[/math]，考虑向量[math]\displaystyle{ \vec{b}=\begin{bmatrix}\mathrm{sgn}(a_1)|a_1|^{p-1}&\mathrm{sgn}(a_2)|a_2|^{p-1}&\cdots&\mathrm{sgn}(a_n)|a_n|^{p-1}\end{bmatrix}^\mathrm{T} }[/math]，得：

[math]\displaystyle{ \|\vec{a}\|_p\|\vec{b}\|_q=\left(|a_1|^p+|a_2|^p+\cdots+|a_n|^p\right)^\frac1p\left(|a_1|^{(p-1)q}+|a_2|^{(p-1)q}+\cdots+|a_n|^{(p-1)q}\right)^\frac1q }[/math] [math]\displaystyle{ =\left(|a_1|^p+|a_2|^p+\cdots+|a_n|^p\right)^\frac1p\left(|a_1|^p+|a_2|^p+\cdots+|a_n|^p\right)^\frac{p-1}{p} }[/math] [math]\displaystyle{ =|a_1|^p+|a_2|^p+\cdots+|a_n|^p }[/math] [math]\displaystyle{ =\vec{a}\cdot\vec{b} }[/math]

由于[math]\displaystyle{ \vec{a}=\frac1q\nabla f_q(\vec{b}) }[/math]，由范数的性质，当任意向量[math]\displaystyle{ \vec{c} }[/math]满足[math]\displaystyle{ \|\vec{c}\|_q=\|\vec{b}\|_q }[/math]时，[math]\displaystyle{ \vec{a}\cdot\vec{c}\leq\vec{a}\cdot\vec{b} }[/math]。由此得任意非零向量[math]\displaystyle{ \vec{c} }[/math]满足[math]\displaystyle{ \frac{\vec{a}\cdot\vec{c}}{\|\vec{c}\|_q}\leq\frac{\vec{a}\cdot\vec{b}}{\|\vec{b}\|_q}=\|\vec{a}\|_p }[/math]，即[math]\displaystyle{ \|\vec{a}\|_p=\sup\left\{x\left|x=\frac{\vec{a}\cdot\vec{b}}{\|\vec{b}\|_q},\vec{b}\neq\vec{0}\right.\right\} }[/math]。同理可证[math]\displaystyle{ \|\vec{b}\|_q=\sup\left\{x\left|x=\frac{\vec{a}\cdot\vec{b}}{\|\vec{a}\|_p},\vec{a}\neq\vec{0}\right.\right\} }[/math]。

极限情况：对于1范数，考虑[math]\displaystyle{ \vec{b}=\begin{bmatrix}\mathrm{sgn}(a_1)&\mathrm{sgn}(a_2)&\cdots&\mathrm{sgn}(a_n)\end{bmatrix} }[/math]，则[math]\displaystyle{ \|\vec{b}\|_\infty=1 }[/math]，[math]\displaystyle{ \vec{a}\cdot\vec{b}=\|\vec{a}\|_1 }[/math]。对于任意非零向量[math]\displaystyle{ \vec{c} }[/math]，[math]\displaystyle{ \frac{\vec{a}\cdot\vec{c}}{\|\vec{c}\|_\infty}=\frac{\sum_ia_ic_i}{\|\vec{c}\|_\infty}\leq\frac{\sum_i\left|a_i\|\vec{c}\|_\infty\right|}{\|\vec{c}\|_\infty}=\|\vec{a}\|_1 }[/math]。对于∞范数，设[math]\displaystyle{ \|\vec{a}\|_\infty=|a_m| }[/math]，考虑[math]\displaystyle{ b_i=\left\{\begin{matrix}\mathrm{sgn}(a_m)&,i=m\\0&,i\neq m\end{matrix}\right. }[/math]，则[math]\displaystyle{ \|\vec{b}\|_1=1 }[/math]，[math]\displaystyle{ \vec{a}\cdot\vec{b}=\|\vec{a}\|_\infty }[/math]。对于任意非零向量[math]\displaystyle{ \vec{c} }[/math]，[math]\displaystyle{ \frac{\vec{a}\cdot\vec{c}}{\|\vec{c}\|_1}=\frac{\sum_ia_ic_i}{\|\vec{c}\|_1}\leq\frac{\sum_i\left|\|\vec{a}\|_\infty c_i\right|}{\|\vec{c}\|_1}=\|\vec{a}\|_\infty }[/math]。

推论：欧式范数的对偶为自身。

定理2：若[math]\displaystyle{ f(\vec{a}) }[/math]与[math]\displaystyle{ g(\vec{b}) }[/math]为对偶，则斜范数（skewed norm）[math]\displaystyle{ f_s(\vec{a})=f(\boldsymbol{A}\vec{a}) }[/math]的对偶为[math]\displaystyle{ g_s(\vec{b})=g\left(\left(\boldsymbol{A}^{-1}\right)^\mathrm{T}\vec{b}\right) }[/math]，其中[math]\displaystyle{ \boldsymbol{A}_{n,n} }[/math]为可逆矩阵。

证明：[math]\displaystyle{ \vec{a}\cdot\vec{b}=\vec{b}^\mathrm{T}\vec{a}=\vec{b}^\mathrm{T}\boldsymbol{A}^{-1}\boldsymbol{A}\vec{a}=(\boldsymbol{A}\vec{a})\cdot\left(\left(\boldsymbol{A}^{-1}\right)^\mathrm{T}\vec{b}\right) }[/math]。

定理3：欧式斜范数[math]\displaystyle{ f(\vec{a})=|\boldsymbol{A}\vec{a}| }[/math]的对偶为[math]\displaystyle{ g(\vec{b})=\left|\left(\boldsymbol{A}^+\right)^\mathrm{T}\vec{b}\right| }[/math]，其中[math]\displaystyle{ \boldsymbol{A}_{m,n} }[/math]为列满秩矩阵。

证明：必然存在可逆矩阵[math]\displaystyle{ \boldsymbol{B}_{n,n} }[/math]、正交矩阵[math]\displaystyle{ \boldsymbol{O}_{m,m} }[/math]和列满秩矩阵[math]\displaystyle{ \boldsymbol{C}_{m,m-n} }[/math]，使[math]\displaystyle{ \begin{bmatrix}\boldsymbol{A}&\boldsymbol{C}\end{bmatrix}=\boldsymbol{O}\begin{bmatrix}\boldsymbol{B}&\boldsymbol{0}\\ \boldsymbol{0}&\mathbf{E}\end{bmatrix} }[/math]，其中[math]\displaystyle{ \mathbf{E} }[/math]为单位矩阵，[math]\displaystyle{ \boldsymbol{B} }[/math]的阶数与[math]\displaystyle{ \boldsymbol{A} }[/math]的列数相等。

[math]\displaystyle{ \begin{matrix} & & \begin{bmatrix}\vec{a}_{n,1}\\ \boldsymbol{0}_{m-n,1}\end{bmatrix} \\ & \begin{bmatrix}\boldsymbol{B}_{n,n}&\boldsymbol{0}_{n,m-n}\\ \boldsymbol{0}_{m-n,n}&\mathbf{E}_{m-n,m-n}\end{bmatrix} & \begin{bmatrix}\boldsymbol{B}\vec{a}_{n,1}\\ \boldsymbol{0}_{m-n,1}\end{bmatrix} \\ \boldsymbol{O}_{m,m} & \begin{bmatrix}\boldsymbol{A}_{m,n}&\boldsymbol{C}_{m,m-n}\end{bmatrix} & \boldsymbol{A}\vec{a}_{m,1} \end{matrix} }[/math]

则[math]\displaystyle{ f(\vec{a})=|\boldsymbol{B}\vec{a}| }[/math]，其对偶为[math]\displaystyle{ g(\vec{b})=\left|\left(\boldsymbol{B}^{-1}\right)^\mathrm{T}\vec{b}\right| }[/math]，且[math]\displaystyle{ \boldsymbol{A}^\mathrm{T}\boldsymbol{C}=\begin{bmatrix}\boldsymbol{B}^\mathrm{T}&\boldsymbol{0}_{n,m-n}\end{bmatrix}\boldsymbol{O}^\mathrm{T}\boldsymbol{O}\begin{bmatrix}\boldsymbol{0}_{n,m-n}\\ \mathbf{E}_{m-n}\end{bmatrix}=\begin{bmatrix}\boldsymbol{B}^\mathrm{T}&\boldsymbol{0}_{n,m-n}\end{bmatrix}\begin{bmatrix}\boldsymbol{0}_{n,m-n}\\ \mathbf{E}_{m-n}\end{bmatrix}=\boldsymbol{0}_{n,m-n} }[/math]，[math]\displaystyle{ \begin{bmatrix}\boldsymbol{A}&\boldsymbol{C}\end{bmatrix} }[/math]为可逆矩阵，且[math]\displaystyle{ \boldsymbol{A} }[/math]与[math]\displaystyle{ \boldsymbol{C} }[/math]列空间正交。

设[math]\displaystyle{ \begin{bmatrix}\boldsymbol{A}&\boldsymbol{C}\end{bmatrix}^{-1}=\begin{bmatrix}\boldsymbol{D}_{n,m}\\ \boldsymbol{F}_{m-n,m}\end{bmatrix} }[/math]，其中[math]\displaystyle{ \boldsymbol{D} }[/math]的行数与[math]\displaystyle{ \boldsymbol{A} }[/math]的列数相等。

[math]\displaystyle{ \begin{bmatrix}\boldsymbol{D}\\ \boldsymbol{F}\end{bmatrix}=\begin{bmatrix}\boldsymbol{B}&\boldsymbol{0}\\ \boldsymbol{0}&\mathbf{E}_{m-n}\end{bmatrix}^{-1}\boldsymbol{O}^{-1}=\begin{bmatrix}\boldsymbol{B}^{-1}&\boldsymbol{0}\\ \boldsymbol{0}&\mathbf{E}_{m-n}\end{bmatrix}\boldsymbol{O}^{-1} }[/math]，[math]\displaystyle{ \boldsymbol{D}=\begin{bmatrix}\boldsymbol{B}^{-1}&\boldsymbol{0}_{n,m-n}\end{bmatrix}\boldsymbol{O}^{-1} }[/math]，[math]\displaystyle{ g(\vec{b})=\left|\boldsymbol{D}^\mathrm{T}\vec{b}\right| }[/math]，又[math]\displaystyle{ \begin{bmatrix}\boldsymbol{D}\\ \boldsymbol{F}\end{bmatrix}\begin{bmatrix}\boldsymbol{A}&\boldsymbol{C}\end{bmatrix}=\mathbf{E}_{m} }[/math]，[math]\displaystyle{ \boldsymbol{D}\begin{bmatrix}\boldsymbol{A}&\boldsymbol{C}\end{bmatrix}=\begin{bmatrix}\mathbf{E}_{n}&\boldsymbol{0}_{n,m-n}\end{bmatrix} }[/math]，[math]\displaystyle{ \boldsymbol{D}=\boldsymbol{A}^+ }[/math]，得证。

范数优化调律 norm-optimized tuning

参考：Dave Keenan & Douglas Blumeyer's guide to RTT/All-interval tuning schemes

目标：最小化损害[math]\displaystyle{ \frac{|\overleftarrow{r}\vec{\mathrm{i}}|}{f(\vec{\mathrm{i}})} }[/math]的上界，其中[math]\displaystyle{ f }[/math]为范数函数。根据对偶范数定义，即最小化[math]\displaystyle{ \mathrm{dual}_f\left(\overleftarrow{r}^\mathrm{T}\right) }[/math]。