gamma-two 分解范数

形式陈述 ​

对 $m,n\ge 1$ 的实矩阵理路矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。 $M\in {\mathbb{R}}^{m\times n}$，考虑任意有限维实内积空间理路内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。中的向量 $u_1,\dots ,u_m$ 与 $v_1,\dots ,v_n$，使

gamma-two 分解范数定义为

中间维数无需预先固定，也不必超过矩阵的秩理路线性映射的秩Rank of a linear map · Matrix rank线性映射像空间的维数，表示其保留下来的独立输出方向数。：先把所有 $u_i$ 投影到 $v_j$ 张成的空间，它们与各 $v_j$ 的内积决定其坐标，故这些投影的张成维数等于行秩；再把各 $v_j$ 投影到这个张成空间，两侧长度均不增加。对非零 $M$，把 $U$ 乘以 $t>0$、$V$ 除以 $t$ 可平衡两侧最大行范数；零矩阵直接取零向量。等价半定规划寻找半正定 Gram 矩阵理路正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。

并最小化 $c$，约束 $G_{kk}\le c$；平衡后最优 $c$ 就是 ${\gamma }_2(M)$。这是矩阵分解范数，不是 Talagrand generic chaining 中同名的 ${\gamma }_2$ functional：后者以度量空间的 admissible partitions 定义，变量和用途均不同。

另一个有用刻画是

其中 $\circ$ 是逐项乘积，$\Vert \cdot {\Vert }_{\mathrm{tr}}$ 是奇异值理路奇异值分解Singular value decomposition · SVD任意有限维线性映射都可在正交规范基下表示为非负对角伸缩。之和，即这里所称的核范数。此加权核范数刻画见 Lee–Shraibman §2.3。它解释了该范数为何能把矩阵的困难子块加权突出。

加权刻画还给出常用的秩界。记 $B=M\circ a{b}^{\mathsf{T}}$，则 $\mathrm{rank}(B)\le \mathrm{rank}(M)$；对其奇异值使用Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，

这里 $\Vert M{\Vert }_{max}=\underset{ij}{max}|M_{ij}|$，$\Vert B{\Vert }_F$ 是各条目平方和的平方根。故 ${\gamma }_2(M)\le \sqrt{\mathrm{rank}(M)}\Vert M{\Vert }_{max}$。对符号矩阵，逐项最大值为一，便得到下面使用的秩下界。