是什么意思∥一个∥p= (∑n我= 1|一种一世(吨)|p)1p‖a‖p=(∑i=1n|ai(t)|p)1p?

机器算法验证 描述性统计 符号
2022-03-30 08:24:16

是什么意思ap=(i=1n|ai(t)|p)1p?

这个公式在改进的数据流摘要:Count-Min Sketch and its Applications(可在此处找到)的第五页中提到我正在实现 Count-Min Sketch 并且可以很好地理解基本概念,但是根据这个等式和我不熟悉的其他一些术语来解释一些更精细的点。

3个回答

这是Lp规范。例如参见维基百科文章:

如果你使用p=2,你会发现它解析为更熟悉的欧几里得范数——即最熟悉的用作向量长度的度量a. p 的其他值给出了文章中概述的其他测量长度的方法——参见欧几里得范数、出租车范数等部分。

这篇论文似乎没有使用Lp以任何基本的方式规范——每一个结果都参考了L1明确的规范。问题本身决定了使用哪种规范。在这种情况下,兴趣集中在多集的基数上。多重集表示为其元素计数的向量,因此它的基数恰好与其相同L1规范。通常,针对一个规范证明的结果可能无需对大范围的证明进行任何更改即可成立p(通常1p)。免费获得更大普遍性的机会将导致许多这样的论文谈论Lp规范。

Lp规范在希尔伯特和巴纳赫空间理论中的对偶性讨论中产生了自己的影响。高级但介绍性的(这并不矛盾!)有关分析的书籍通常会彻底涵盖这些材料。有关这些规范之间的一些关系的介绍,请阅读Holder 不等式Minkowski 不等式

||a||表示定义在向量空间上的特定函数,称为norm 。它映射了一个n向量空间的维元素转换为非负实数。||a||p表示在向量空间上定义的一个特殊范数。V是一个向量空间。任何功能p:VR+, 也表示p(v)||v||这样

  1. p是有限和凸的
  2. p(x)=0x=0
  3. αR,xV,p(αx)=|α|p(x)

被称为规范V(V,p)(V,||||则称为范数空间。您可以检查您的函数是否满足所有这些属性。在你的例子中,V是一个函数空间,即ai:TT. 这是您可能熟悉的欧几里德空间(带有欧几里得范数)的概括,这只是范数空间的一个特例,其中基础集合是(n维)实数,范数是所谓的欧几里得范数,您的问题中出现的函数的一个特例。

例如,欧几里得平面是一个范数空间,使得V=R2,x=(x1,x2)R2, 并定义范数R2作为p(x)=||x||2=||x||=(x1+x2)2=(i=12xi2)1/2. 所以它只是一个平面,范数给出了向量的“大小”。请注意,这只是您提到的规范的一个特例,这样n=2,p=2,ai(x)=xi,并且您不需要绝对值运算符,因为它是平方项之和。

这些主题在范数或范数空间标题下的实分析或线性代数(以更受限制的方式)教科书中都有介绍。