Kronecker 逼近定理的应用

作者: 远处的光 | 来源:发表于2025-01-02 15:56 被阅读0次

产品经理如何应用贝叶斯定理？（来源于网络）
三角函数
ElitesAI·机器学习进阶打卡第一天2020-02-17
卷积神经网络-Question
无标题文章
Rice定理的应用范围
逻辑代数的基本定理
生活准则
matlab的kron函数（kronecker乘积）
任政非 : “一个人一辈子能做成一件事已经很不简单。”

2025.01.03 Friday @BJ

上一篇回顾了“圆周率整数倍的小数部分”，这个结论的一般情形是 Kronecker 逼近定理，我最近的两篇论文都用到这个结论，一篇是已经发表在 ICML2024 上的，用来构造函数逼近的有限词汇表，另一篇是在投的论文，也是构造逼近性质的。

下面来考虑两个问题：

问题 1：对于矩阵 $M \in \mathbb{R}^{d \times n}$ ，何时有 $M \mathbb{N}^n = \{M z | z \in \mathbb{N}^n \}$ 在 $\mathbb{R}^{d}$ 中稠密？
问题 2：对于矩阵 $M \in \mathbb{R}^{d \times n}$ ，何时有 $M \mathbb{Z}^n = \{M z | z \in \mathbb{Z}^n \}$ 在 $\mathbb{R}^{d}$ 中稠密？

显然，当 $n \le d$ 时是不可能稠密的，因此只要考虑 $n =d+m, m\ge 1,$ 的情形。

由 Kronecker 逼近定理，假设矩阵 $A\in\mathbb{R}^{d \times m}$ 的 $d$ 个 $m$ 维行向量与坐标向量一起是有理线性无关的，即：
$\quad A^T \mathbf{k} \in \mathbb{Z}^m, \quad \mathbf{k} \in \mathbb{Z}^d \quad 当且仅当 \quad \mathbf{k} = 0,$
则有 $A \mathbb{Z}^m + \mathbb{Z}^d$ 在 $\mathbb{R}^{d}$ 中稠密（备注：而且可以证明是等分布的）。

于是乎，取 $M= [A, I_d]$ ，以及 $W = [A^T, I_m]$ 则有下面的推论：

推论：矩阵 $M= [A, I_d] \in \mathbb{R}^{d \times (d+m)}$ 使得 $M \mathbb{Z}^{d+m}= \{M z | z \in \mathbb{Z}^{d+m} \}$ 在 $\mathbb{R}^{d}$ 中稠密，当且仅当矩阵 $W = [A^T, I_m] \in \mathbb{R}^{m \times (d+m)}$ 满足 $\{ z\in \mathbb{Z}^{d+m} | W z= \mathbf{0} \} = \{ \mathbf{0} \}$ .

举个例子：经典版本的 Kronecker 逼近定理指出，如果 $1, \alpha_1, ..., \alpha_n$ 在 $\mathbb{Z}$ 上线性无关，则当 $q$ 取遍全体整数时， $(\{q \alpha_1\},...,\{q \alpha_d\})$ 在 $[0,1]^d$ 中是稠密的。写成矩阵的版本，是取 $m=1$ ， $A^T = [\alpha_1,...,\alpha_d]$ ，以及
$M =\begin{pmatrix} \alpha_1 &1 & 0& ... & 0\\ \alpha_2 &0 & 1 &... & 0\\ ... &... & ... &... & ...\\ \alpha_d &0 & 0 &... & 1\\ \end{pmatrix}.$

回到问题 1 和问题 2，两个问题的区别在于取全体自然数还是取全体整数。对于上面这个特殊的矩阵 $M$ ，如果 $\alpha_1,...,\alpha_d$ 都是负数，则该矩阵 $M$ 同时满足问题 1 和问题 2 的要求。也就是说，最小的 $n$ 就是取 $n=d+1$ 。

如果只是要构造一个矩阵 $M$ ，那么上面的矩阵 $M$ 就够了。如果是要找出矩阵 $M$ 要满足的充要条件，那就得再进一步讨论一下。

首先，上面的推论已经对 $M=[A,I_d]$ 的情形给出了充要条件，只是假定了 $M$ 具有特定的分块形式。注意到将矩阵 $M$ 换成 $QMP$ 并不会影响稠密性，只要 $Q \in \mathbb{R}^{d\times d}$ 是非奇异矩阵， $P \in \mathbb{R}^{(d+m)\times (d+m)}$ 是置换矩阵。而任何秩为 $d$ 的矩阵 $M$ 都可以写为 $Q[A, I_d] P$ 的形式，因此对于问题 2，我们可以写出完整的答案如下：

问题 2 答案：对于秩为 $d$ 的矩阵 $M \in \mathbb{R}^{d \times (d+m)}$ ，存在可逆矩阵 $Q\in \mathbb{R}^{d\times d}$ 和置换矩阵 $P \in \mathbb{R}^{(d+m)\times (d+m)}$ 使得 $M=Q[A, I_d] P$ 。要使 $M \mathbb{Z}^{d+m} = \{M z | z \in \mathbb{Z}^{d+m} \}$ 在 $\mathbb{R}^{d}$ 中稠密，当且仅当矩阵 $W = [A^T, I_m] \in \mathbb{R}^{m \times (d+m)}$ 满足 $\{ z\in \mathbb{Z}^{d+m} | W z= \mathbf{0} \} = \{ \mathbf{0} \}$ .

对于问题 1，由于指标限定取自然数，不能取负的整数，所以需要对 $M$ 再加些条件。

当 $M=[A,I_d]$ 的情形，检查 Kronecker 逼近定理的证明，实际上有下面的结论：

推论 '：矩阵 $M= [A, I_d] \in \mathbb{R}^{d \times (d+m)}$ 使得 $M (\mathbb{N}^{m} \times \mathbb{Z}^{d})= \{A z_1 + z_2 | z_1 \in \mathbb{N}^{m}, z_2 \in \mathbb{Z}^{d} \}$ 在 $\mathbb{R}^{d}$ 中稠密，当且仅当矩阵 $W = [A^T, I_m] \in \mathbb{R}^{m \times (d+m)}$ 满足 $\{ z\in \mathbb{Z}^{d+m} | W z= \mathbf{0} \} = \{ \mathbf{0} \}$ .

这里对 $A$ 的条件没有变，只是将 $M \mathbb{Z}^{d+m}$ 换成了 $M (\mathbb{N}^{m} \times \mathbb{Z}^{d})$ 。为了将 $A z_1 + z_2$ 中的 $z_2$ 也能换成自然数，关键是避免 $Mz, z\in\mathbb{N}^{d+m},$ 有的分量被限制在了半空间中。

举个例子：形如 $k_1 \sqrt{2} - k_2, k_i \in \mathbb{N}$ , 的数在 $\mathbb{R}$ 中是稠密的，但形如 $k_1 \sqrt{2} + k_2, k_i \in \mathbb{N}$ , 的数在 $\mathbb{R}$ 中不是稠密的（实际上是离散的）。

一般情形，似乎再加个条件 $M \mathbb{R}^{d+m}_+ = \mathbb{R}^d$ 就可以了。显然这是个必要条件。充分性的话，以后有空再讨论吧。

产品经理如何应用贝叶斯定理？（来源于网络）
贝叶斯定理提供的是一种逆条件概率的方法，本文简单总结了贝叶斯定理是什么，贝叶斯定理应用的理解，以及贝叶斯定理在AI...
三角函数
余弦定理定理应用余弦定理是解三角形中的一个重要定理，可应用于以下三种需求：当已知三角形的两边及其夹角，可由余...
ElitesAI·机器学习进阶打卡第一天2020-02-17
1、普适逼近定理：多层感知器能够以任意精度逼近任意一个定义在闭集的连续函数 2、反向传播算法和多层感知机 3、浏...
卷积神经网络-Question
1. 为什么说神经网络可以逼近任意函数？万能逼近定理的核心主张是，在有足够多的隐藏神经元的情况下，存在着一组可以...
无标题文章
17.1勾股定理(第1课时一、内容和内容解析 1.内容勾股定理的探究、证明及简单应用. 2.内客解析勾股定理...
Rice定理的应用范围
Turing著名的停机定理说明无法用有限时长的算法判定任意的计算机程序是否停机产生确定输出，这意味着你无法将某些...
逻辑代数的基本定理
逻辑代数的基本定理逻辑代数的基本定理是应用划归逻辑表达式的关键。吸收律A + AB = AA + !AB = A...
生活准则
上图是统计学中的一个公式—贝叶斯定理贝叶斯定理在统计学中应用广泛，而如果把它的原理应用到生或中，绝对是...
matlab的kron函数（kronecker乘积）
转自360百科：kron_360百科矩阵的Kronecker乘法对n×m阶矩阵A和p×q阶矩阵B，A和B的Kr...
任政非 : “一个人一辈子能做成一件事已经很不简单。”
“随着逐步逼近香农定理、摩尔定律的极限，面对大流量、低延时的理论还未创造出来，华为已感到前途茫茫，找不到方向。” ...