以下内容全部摘自维基百科或教科书。
 为了后续查阅方便，故此记录。
 
1. 集合
 
1.1 σ代数
 
某个集合 X 上的σ-代数又叫 σ-域，是 X 的幂集的子集合（X 的幂集即包含所有 X 的子集的集合系）。这个子集满足对于补集运算和可数个并集运算的封闭性（因此对于可数个交集运算也是封闭的）。σ-代数在测度论里可以用来定义所谓的“可测集合”，是测度论的基础概念之一。
 

 简单来说，σ-代数就是定义在X上的，一种特殊的集合的集合。
 
2. 拓扑学
 
2.1 拓扑
 
定义：
 $X$是一个集合，$X$上的拓扑（topography）$T$是$X$的子集族，且满足以下条件：
 
 
2.2 拓扑空间
 
定义：
 指定了拓扑$T$的集合$X$被称为拓扑空间（topology space）。
 
可见，拓扑空间就是集合$X$本身，如果$X$被指定了一个拓扑。
 
集合$X$及定义在$X$上的拓扑$T$是拓扑空间的两个要素，因此在正式场合用$(X,T)$代表拓扑空间。
 
2.3 开集 & 闭集
 
开集系 & 开集
 
定义
 设拓扑空间$(X,T)$有子集$O$,若$O\in T$,则$O$称为开子集（open set）。
 

 下面是维基百科的内容，实际上是一个意思，不过还是上面的知乎回答清楚一些。
 
X的子集的集合族D被称为开集系（其中的元素称为开集），当且仅当其满足如下开集公理：
 
空集和X都属于D
 
对任意并运算封闭
 
对有限交运算封闭
 
 
从开集出发定义其它各概念：
 
 闭集：
 X和开集做差。
 
邻域：
 开集O属于U，点x只有在开集O中才能把U作为邻域。
 
开核：
 U中的开集之并为开核。可见只有点x属于U的开核，U才是x的邻域。
 
闭集系 & 闭集
 
前面是从开集系出发的，其实也可以从闭集系、邻域等概念出发定义其他概念。
 
X的子集的集合族S被称为开集系（其中的元素称为开集），当且仅当其满足如下开集公理：
 
空集和X都属于D
 
对任意交运算封闭
 
对有限并运算封闭
 

 从闭集出发定义其它各概念：
 
 
2.5 拓扑空间的紧致性
 
覆盖
 定义：设X是一个集合，他的一族子集
    
     
      
       
        A
       
       
        =
       
       
        
         {
        
        
         
          
           A
          
          
           λ
          
         
         
          ∣
         
         
          λ
         
         
          ∈
         
         
          Λ
         
        
        
         }
        
       
      
      
       A = \left\{ {{A_\lambda }|\lambda \in \Lambda } \right\}
      
     
    A={Aλ​∣λ∈Λ}如果满足
 
$$\bigcup _{\lambda \in \Lambda }{A}_{\lambda }=X$$
 
则称A为X的一个覆盖。
 
开覆盖
 定义：特别的，如果X是一个拓扑空间，且每个$A_{\lambda }$都是X中的开集，则A为X的一个开覆盖。
 
拓扑空间的紧致性
 拓扑空间 X 被定义为紧致的，如果它的所有开覆盖都有至少一个有限的子覆盖：
 
 意思就是，对于拓扑空间X的任意一个开覆盖C，C的子集也能实现覆盖。
 
局域紧致性
 待补充。
 
2.4 豪斯多夫空间
 
假设X是拓扑空间。设x和y是X中的点。
 
邻域概念回顾
 X是一个集合，比如说是点集。X中的子集包含了X中不同的点。拓扑T就是就是这些子集的集合，满足一些既定条件。T中的元素，也就是X中的一些子集，被称为开集。x是X中的点，假设它在某个开集O之中。U是X的一个子集。如果O包含于U之中，那么U就是点x的邻域。
 
由邻域分离
 如果存在 x 的邻域 U 和 y 的邻域 V 使得 U 和 V 是不相交的 $(U\cap V=\varnothing )$，则称 x 和 y 可以由邻域分离。
 
豪斯多夫空间
 如果X中的任意两个不同的点都可以由这样的邻域分离，那么称 X 是豪斯多夫空间。这也是豪斯多夫空间叫做“T2空间”或“分离空间”的原因。
 
3. 哈尔测度
 
3.1 波莱尔集 & 测量
 
波莱尔代数 & 波莱尔集
 对于一个局域紧致豪斯多夫拓扑群（G,・） ，其所有的紧子集生成的σ-代数被称为波莱尔代数（Borel algebra），波莱尔代数的元素即为波莱尔集。
 
波莱尔集上的变换
 对于群G的元素g和子集S，可以定义S的左变换和右变换：
 
 左/右变换使波莱尔集映射为波莱尔集。
 
变换不变的
 对于一个作用于G的波莱尔子集上的测量μ，如果对所有的波莱尔子集S和所有的g有
 
$$\mu \left(gS\right)=\mu \left(S\right)$$
 
则称这个测度$\mu$是左变换不变的。相应可以定义右变换不变性。
 
3.2 哈尔测度
 
左哈尔测度
 
在差一个正因子常数的情形下，如果G的波莱尔子集上的一个唯一可加的非平凡测度μ满足如下性质：
 
 那么这个G上的测度μ便被称为左哈尔测度。
 
右哈尔测度
 
同样可以证明存在一个唯一（相差一个正因子的意义下）的右变换不变的波莱尔测度ν满足上面的正则条件且在紧致集合上有限，但并不要求它与左变换不变的哈尔测度μ相同。
 
 
3.3 哈尔积分(Haar integral)
 
由勒贝格积分理论，可以定义G上所有波莱尔测度方程$f$的积分。这个积分便是哈尔积分(Haar integral)。 如果μ是一个左哈尔测度，那么对任意一个方程f，都有
 
 
4. 群函数
 
有了这些前置知识，就可以理解论文中的群函数了。
 
待补充。
 
5. 参考链接
 
维基百科：拓扑空间
 知乎：拓扑空间
 维基百科：豪斯多夫空间
 百度文库：拓扑空间的紧性
 维基百科：哈尔测度

这次来说说函数式的数据结构是什么样子的，本章会先用一个list来举例子说明，最后给出一个Tree数据结构的练习，放在公众号里面，练习里面给出了基本的结构，但代码是空缺的需要补上，此外还有预留的testcase可以验证。
 
关注公众号：哈尔的数据城堡，回复“函数式数据结构”可以获得。（写文章不容易，大哥大姐关注下吧[哭笑]）
 
然后是这系列的索引：
 
Scala函数式编程指南（一） 函数式思想介绍
 
scala函数式编程（二） scala基础语法介绍
 
Scala函数式编程（三） scala集合和函数
 
1.什么是函数式的数据结构
 
还记得前面说过，函数式编程最大的特点是什么吗？就是没有副作用。那么函数式的数据结构自然也是如此。
 
无副作用的关键是：
 
一个函数无论调用多少次，只要输入参数相同，则结果也必然相同。
且这个函数执行过程中不会改变程序的任何外部状态，如全局变量，对象的属性等。
函数的结果也不依赖外部状态。
 
在java中，最经典的数据结构ArrayList，是通过一个全局的size变量，来控制ArrayList的大小的，这就说明ArrayList并非无副作用。
 
在scala中，集合（List，Map等）默认是不可变的，以链表List为例，是无法通过push等操作，往一个链表里面添加内容的。只能通过两个链表相加的方式，生成一个新链表（Map也是一样，通过两个Map相加，Key相同的会覆盖，以达到更新的目的）。这点倒是和String有点像。
 
不过其实这样有一个问题，那就是很耗费内存。但这个问题可以用懒加载来解决，限于篇幅，后面再介绍吧。
 
总结一下，函数式的数据结构，最大的特点，就是没有副作用。那么如何实现无副作用的数据结构呢，我们下面用链表的例子来展示。
 
不过在这之前，需要先回顾下一些语法知识。
 
2.scala知识回顾
 
我的一个观点是，语言的语法知识如果只是看，背，而没有实际用到，那是比较难记住的。这里就把这次会用到的语法知识做个简单介绍，如果有需要，可以查阅前面写的前两章。
 
我这里也有演示如果运用前面介绍的语法知识实现一个函数式的List()。
 
PS：如果不想看语法知识可以直接跳到第三节。
 
前面的语法索引：
 
scala函数式编程（二） scala基础语法介绍
 
Scala函数式编程（三） scala集合和函数
 
2.1 scala的模式匹配
 
模式匹配类似于swtch语法，不过它能匹配的不止是值，还有数据类型。同时，它是一个匿名函数，在scala里，函数不用return，能直接返回值。
 
val times = 1

//使用模式匹配来匹配值
times match {
  case 1 => "one"
  case 2 => "two"
  case _ => "some other number"
}

//使用模式匹配，匹配类型，再判断值

times match {
  case i:Int if i == 1 => "one"
  case i:Int if i == 2 => "two"
  case _ => "some other number"
}

 
如果有小伙伴想了解更多，可以看看我这篇，scala模式匹配详细解析。
 
2.2 object和apply
 
前面介绍到，object是一个类的伴生对象，而且相当于static类，内存里只能有一个对象。apply方法则是说，可以在使用object对象的时候，直接默认使用。别说了，看代码：
 
scala> class Foo {}
defined class Foo

//有一个apply方法
scala> object FooMaker {
     |   def apply() = new Foo
     | }
defined module FooMaker

//新建object，自动得就调用了apply
scala> val newFoo = FooMaker() //赋值的对象是Foo，因为调用了FooMaker()的apply 
newFoo: Foo = Foo@5b83f762  

 
上面的代码，FooMaker相当于一个工厂。
 
2.3 scala的泛型
 
scala中的泛型，叫做型变或变性，英文叫variance。主要有三种情况：
 
假设Dog是Animal的子类。那么有如下关系：
 
协变(covariant)：List[Dog]是List[Animal]的子类，形态用一个+号表示，即List[+A]（这里的A是泛指，类似java中的泛型，可以随便指定一个字母）。
逆变(contravariant)：与协变相反，List[Animal]是List[Dog]的子类，形态用一个-号表示，即List[-A]。
不变(invariant)：List[Dog]是List[Animal]的无关，不用任何表示，List[A]。
 
协变是比较符合正常逻辑思考的，一群狗确实也可以说是一群动物。逆变就比较反直觉了，不过这里先不讨论这点，后面有机会再讨论。
 
3.构建函数式的List
 
OK，有了上面的基础，就能够来构建一个函数式的数据结构了，不过在此之前，先让我们回顾下传统的List数据结构。
 
3.1 传统的List
 
还记得以前数据结构是怎样设计的吗？
 
 
最普通的链表，通常都是由一个又一个的Node组成，一个Node中存储数据和下一个链表的变量。最后通过一个空值结尾，通常是Null。
 
在Java中，它的链表Linklist，是通过一个全局变量size来控制链表的。
 
通过for循环实现基础的增删查改等操作。而是，也是传统List的常见写法，但在函数式的List中可不能这样。还记得吗，函数式最大的特点就是无副作用。像java这里用一个全局的size来控制，那可真是万万不可啊，在多线程的情况下还不得崩溃。
 
关于为什么要写无副作用的代码，这里就不做探讨，详细内容可以看看这个系列的第一章。Scala函数式编程指南（一） 函数式思想介绍。
 
3.2 scala实现函数式的List
 
我们要做的是写出无副作用的集合，那要怎么做呢？给5秒钟闭上眼睛好好想一想有没有什么思路。。。
 
可能有的同学会想得到，这个答案就是递归。通过递归，能够避免副作用的产生。如常用的增删查改，如果使用递归，就可以避免使用一个全局变量，当然递归通常都没有直接使用for循环那么直观，所以充满递归的代码初次看会比较晦涩。但如果用多了，你会发现其实函数式的代码，也是非常好懂的。
 
下面，我们来看看如果使用递归实现一个List。
 
3.1 定义基本的类型
 
首先，我们要定义每个节点Node的类型，以及结尾Nil。由于使用到了递归，我们需要让Node和Nil都有同样的父类，因为递归函数的返回都是一样的。
 
如果还是不明白为什么要让Node和Nil为啥要有同样的父类，那不妨先放一放，继续看下去吧。
 
//定义自己的特质（相当于java的接口），泛型使用协变
sealed trait List[+A]

//定义一个case类，作为每一个List的结尾
case object Nil extends List[Nothing] 

//定义List子类，也可以说是List中的每个Node，每个List都是由一个又一个的Cons组成，以Nil结尾
case class Cons[+A](head: A, tail: List[A]) extends List[A]

 
注意第一行定义了List[+A]的特质，和scala集合中的List是区分开来的，只是名字叫一样而已。这个是我们自己的List！！
 
而后定义了Nil和Cons，分别作为List的结尾和Node节点，注意case class也是scala的语法糖，可以理解为java bean。
 
之所以先定义了一个List的特质（接口），再分别用Nil和Cons继承它，是因为在递归的情况下，要让节点和结尾保持同一类型，而这个就是通过多态实现的。
 
3.2 实现List工厂
 
前面说到，通常是用object来作为工厂，这里也是一样的，我们可以定义List工厂。
 
定义工厂方法如下：
 
object List {
  //使用可变长度，如果传进来的参数是空，就返回Nil，否则使用递归返回Cons，注意，这里的apply方法就是使用了递归
  def apply[A](as: A*): List[A] = // Variadic function syntax
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

}
 
这里的apply[A](as: A*)，括号里面的A*的意思，是多个参数的意思，就是说可以有很多个参数，是scala的一个语法糖。
 
在最后
 
 
 
else Cons(as.head, apply(as.tail: _*))
 
 
看到最后面的 _*了吗，这个的意思，是除了第一个参数以外的其他参数，也是语法糖。
 
在这一个小小的地方就用到了递归，不断调用apply方法去解析后面的参数，最终生成一个List。初次看可能会比较迷，可能放在编译器里面运行一下，方便理解。而这种操作在scala函数式编程中，是非常普遍的做法。
 
至此，我们就建立了一个List的数据结构，先来看看我们的成果
 
//一个递归的List
scala> List(1,2,3)
res0: List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
 
现在的List数据结构只是初具雏形，我们还得往里面加方法。
 
3.3 用函数式的方式实现List更多方法
 
通常来说，数据结构比较重要的是增删查改等操作，但因为是不可变的，同时函数式中通常是不改变对象信息的，所以这些基本操作反而不是首要的。
 
我们先来看一个简单些的例子吧，让一个List[Int]中的数据累加。
 
object List {
  ......
  //传入参数是一个Int类型的List，使用模式匹配
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    //使用递归累加
    case Cons(x,xs) => x + sum(xs)
  }
  ......
}

 
这里主要传入的参数是一个Int类型的List，然后使用模式匹配，如果是结尾，则返回0，如果是中间节点，则使用递归累加。
 
上面那个例子比较简单，明白后可以来看看如何为List构建更加通用的方法。通常比较常用的是前面介绍过的诸如map，filter等操作，下面先用一个map来说明一下吧。
 
object List {
  ......
  //Map操作，使用模式匹配
  def map[A,B](list: List[A],f: A => B): List[B] =list match {
    case Nil              ⇒ Nil
    //使用递归
    case Cons(head, tail) ⇒ Cons(f(head), map(tail,f))
  }
  ......
}
 
map函数，需要传进入一个待处理的list，以及一个函数作为参数，用以对List中每个元素做处理。
 
比如说想让List中每个元素+1，那就可以传入
 
 
 
val addOne = (num:Int) => num+1
 
 
还记得之前说，在scala中，函数也能当作变量嘛。将addOne这个函数作为参数，这样就会让List中每个元素都+1，然后返回一个新的List，当然，这个也是用递归实现的。
 
实现代码看起来很简洁，也是用模式匹配，匹配每个元素的类型，就是是Node还是结尾。如果是结尾，直接返回，如果是Node，那么处理完当前数据，递归去处理后面的数据，并返回新的处理后的Node。
 
熟悉以后，会发现这样的处理方式看着很舒服，代码写得也很少，非常简洁。
 
在我看来，这就是递归的魅力所在。
 
除了map之外，还有其他操作处理，包括filter，foldLeft，reduce等操作。我把代码放在我的公众号中，限于篇幅这里就不讲太多。关注公众号：哈尔的数据城堡，回复“函数式数据结”可以获得。
 
代码中使用了隐式转换来扩充List的操作，并演示了如何使用隐式转换，以及如何使用复用来组合功能以实现新的功能。有同学可能不明白为什么简单的List要搞这么复杂，看了代码可能会更加理解。
 
4.函数式的二叉搜索树
 
这部分我是作为练习的，连同List代码放在一块，里面有基本的结构，但一些缺失的内容需要你来补充。相信我，做了一遍，肯定能够对函数式的数据结构有更深的理解。
 
对了，二叉搜索树的练习还有几个test case，做完跑一遍了，如果全过那基本上你写的代码就不会有太大的问题，good luck~
 
再说一遍我把练习的代码放在了我的公众号中，关注公众号：哈尔的数据城堡，回复“函数式数据结构”就能免费获得啦。
 
下一篇会再针对List和Tree的代码来讲一讲，有不明白的地方到时候也可以看看。
 
以上~~
 
 
推荐阅读：
 通俗得说线性回归算法（一）线性回归初步介绍
 通俗得说线性回归算法（二）线性回归初步介绍
 大数据存储的进化史 --从 RAID 到 Hadoop Hdfs
 C，java，Python，这些名字背后的江湖！

 
正定函数
 
 


    

     zhengding hanshu
     

     正定函数
positive definite function
     

     
   指实轴
     上定义的满足如下条件的连续函数
     ：
     
　　　 [835-05]
     这里“正定”名称来源于正定矩阵。事实上,式(1)等价于说,对一切
     与一切点列[835-06]
     ,复数矩阵[835-7]
     [835-07]
     是一个正定矩阵（严格地说是半正定矩阵）。
     
　正定函数概念的提出晚于它的一个同类，即所谓正定序列。O.特普利茨于20世纪初首先定义了正定序列的概念,即它是使矩阵[835-08]
     正定的序列[835-09]
     。G.赫格洛茨随后发现了正定序列的一个非常重要的性质。正是在此基础上,S.博赫纳于30年代初得到了
     上正定函数的重要性质，并第一个认识到了这个概念的重要性。他在这方面的重要贡献之一便是建立了类似赫格洛茨定理的下述结果:
     上连续函数
     (
     )是正定的，当且仅当存在有界增函数
     (
     )，使
     
　　　　　[835-10]
     　　　　　　　(2)
     
　正定函数的概念可以允许下述推广。首先,函数
     的定义域可以不必是
     ，而是任意的局部紧
     
     群
     。正定函数的概念推广到这样的群上是直接的。也就是说,
     上连续函数
     称为是正定的（记其全体为
     (
     )），若
     
　　　　[835-11]
     
     
                [835-110]
      　　　　　(1)＇在这样的推广下，正定序列与正定函数的概念便获得了统一：前者是整数群
     上的正定函数，后者是实轴群
     上的正定函数。正定函数概念的第二个推广是函数 
     可以不必是连续的，而只要求是可测的（这里可测性是关于所在群
     的哈尔测度）。正如 F.（F.）里斯、I.E.西格尔与J.冯·诺伊曼等先后指出的，这样的正定函数与连续的正定函数只相差一个局部零（即在任意紧集上都几乎处处为零）的正定函数。第三个推广是将式 (1)（或（1）＇）左边的和改为积分。仍以 
     为例。
     上波莱尔可测函数[kg2]
     
     [kg1]
     称为正定的，如果对一切
     [kg1]
     
     [kg1]
     
     
     （
     ），总有
     (
     -
     )
     (
     )
     (
     )[kg1]
     
     [kg1]
     
     
     (
     ×
     ),且
     
　　　　[835-12]
      　　　　(3)可以证明，式(3)意义下的正定函数与式(1)意义下的正定函数是几乎处处相等的。特别地，两种意义下连续的正定函数的集合是一样的。
     
　正定函数是一个在许多领域都会遇到并且很有用的概念。如概率论中随机变量的特征函数就是正定函数。特征函数比随机变量的分布函数更易于处理。P.莱维正是用正定函数作工具对独立随机变量和的中心极限定理进行了比较统一完整的处理。正定函数在泛函分析中也经常遇到。事实上连续正定函数与某种连续正泛函一一对应。以
     情况为例,
     上连续正定函数
     与
     (
     )(
     上有界波莱尔测度所构成的对合巴拿赫代数)上连续正泛函
     
　　　  [835-13]
     　　　(4)是一一对应的。此外，正定函数在调和分析中的地位也十分突出。交换群上的调和分析中的许多基本事实的建立都得力于正定函数这个概念。例如，傅里叶逆转定理便叙述为
     
[835-14]
     式中∧表示傅里叶变换，∨表示傅里叶逆变换，
     表示
     的对偶群。又如，普朗歇尔定理（它说，傅里叶变换是
     
     (
     )到
     
     (
     )上的一个等距同构）的一个证明便利用了上述逆转定理以及如下事实
     
　　　[835-15]
     式中*表示卷积,
     (
     )是
     (
     )生成的复线性空间
     至于在非交换群上的调和分析中，由于正定函数与连续酉表示的密切关系，以及它比连续酉表示更具体，它的作用也显得越来越重要。此外，正定函数在复变函数、积分方程、微分方程的边值问题、信息论等领域也都十分有用。
     
　参考书目
     
E. Hewittand  K. A. Ross, abstract HarmonicAnalysis,Vol.2, 2nd ed., Springer-Verlag, Berlin,1970.
     
J. Stewart, PositiveDefinite  Functions  andGeneralizations, An Historical Survey, The RockyMountain Journal of Mathematics, Vol.6, pp.409～434, 1976.
     
　　　　　　　　　　　　　　　　　龙瑞麟
    

小波变换的基本思想是用一组小波函数或者基函数表示一个函数或者信号，例如图像信号。为了理解什么是小波变换，下面用一个具体的例子来说明小波变换的过程。 
1. 求有限信号的均值和差值
 
   [例8. 1] 假设有一幅分辨率只有4个像素 的一维图像，对应的像素值或者叫做图像位置的系数分别为： 
                   [9  7  3  5]
  计算它的哈尔小波变换系数。
 
计算步骤如下：
     步骤1：求均值(averaging)。计算相邻像素对的平均值，得到一幅分辨率比较低的新图像，它的像素数目变成了2个，即新的图像的分辨率是原来的1/2，相应的像素值为：
 
            [8 4]
 
步骤2：求差值(differencing)。很明显，用2个像素表示这幅图像时，图像的信息已经部分丢失。为了能够从由2个像素组成的图像重构出由4个像素组成的原始图像，就需要存储一些图像的细节系数(detail coefficient)，以便在重构时找回丢失的信息。方法是把像素对的第一个像素值减去这个像素对的平均值，或者使用这个像素对的差值除以2。在这个例子中，第一个细节系数是(9-8)=1，因为计算得到的平均值是8,它比9小1而比7大1，存储这个细节系数就可以恢复原始图像的前两个像素值。使用同样的方法，第二个细节系数是(3-4)=-1，存储这个细节系数就可以恢复后2个像素值。因此，原始图像就可以用下面的两个平均值和两个细节系数表示，
 
               [8 4 1 -1]
 
步骤3：重复第1，2步，把由第一步分解得到的图像进一步分解成分辨率更低的图像和细节系数。在这个例子中，分解到最后，就用一个像素的平均值6和三个细节系数2,1和-1表示整幅图像。
 
               [6  2  1  -1]
 
这个分解过程如表8-1所示。
 
表8-1 哈尔变换过程
 
 
 
 
分辨率
 
 
平均值
 
 
细节系数
 
 
4
 
 
[9  7  3  5]
 
 
 
 
 
2
 
 
[8  4]
 
 
[1  -1]
 
 
1
 
 
[6]
 
 
[2]
 
 
 
 
 
    由此可见，通过上述分解就把由4像素组成的一幅图像用一个平均像素值和三个细节系数表示，这个过程就叫做哈尔小波变换(Haar wavelet transform)，也称哈尔小波分解(Haar wavelet decomposition)。这个概念可以推广到使用其他小波基的变换。
     从这个例子中我们可以看到：
   ① 变换过程中没有丢失信息，因为能够从所记录的数据中重构出原始图像。
   ② 对这个给定的变换，我们可以从所记录的数据中重构出各种分辨率的图像。例如，在分辨率为1的图像基础上重构出分辨率为2的图像，在分辨率为2的图像基础上重构出分辨率为4的图像。
   ③ 通过变换之后产生的细节系数的幅度值比较小，这就为图像压缩提供了一种途径，例如去掉一些微不足道的细节系数并不影响对重构图像的理解。