第1章 引言 1
第2章 高维空间 3
2.1 高维空间的性质 6
2.2 高维球体 6
2.2.1 高维空间的球体和立方体 7
2.2.2 单位球体的体积和表面积 8
2.2.3 体积在赤道附近 11
2.2.4 体积在一个狭窄的环内 14
2.2.5 表面积在赤道附近 14
2.3 其他立方体的体积 16
2.4 在球体表面随机生成均匀分布的点 17
2.5 高维中的高斯分布 18
2.6 尾概率的界限 25
2.7 随机投影和Johnson-Lindenstrauss定理 27
文献标记 30
练习 31
第3章 随机图 38
3.1 G（n,p）模型 38
3.1.1 度数分布 40
3.1.2 图G（n,d/n）中的三角形 44
3.2 相变 46
3.3 巨型分支 53
3.4 分支过程 60
3.5 回路和全连通 66
3.5.1 回路的出现 66
3.5.2 全连通性 67
3.5.3 直径O（ln n）的阈值 69
3.6 单调性的相变 71
3.7 CNF可满足性的相变 73
3.8 随机图的非均匀模型和成长模型 78
3.8.1 非均匀模型 78
3.8.2 给定度数分布的随机图中的巨型分支 78
3.9 增长模型 80
3.9.1 无优先连接的增长模型 80
3.9.2 具有优先连接的增长模型 88
3.10 小世界效应图 89
文献标记 93
练习 93
第4章 奇异值分解（SVD） 103
4.1 奇异向量 104
4.2 奇异值分解（SVD） 108
4.3 最佳k阶逼近 110
4.4 计算奇异值分解的幂方法 112
4.5 奇异值分解的应用 116
4.5.1 主元分析 116
4.5.2 球形正态混合的聚类分析 117
4.5.3 应用SVD于一个离散优化问题 122
4.5.4 谱分解 125
4.5.5 奇异向量和文件评级 125
文献注记 126
练习 127
第5章 随机行走和Markov链 134
5.1 平稳分布 137
5.2 电路网络和随机行走 139
5.3 具有单位边权重的无向图上的随机行走 144
5.4 欧几里得空间中的随机行走 151
5.5 作为Markov链的万维网 154
5.6 Markov链Monte Carlo方法 158
5.6.1 Metropolis-Hastings算法 162
5.6.2 Gibbs取样 163
5.7 无向图上随机行走的收敛性 165
文献注记 173
练习 173
第6章 学习及VC维 182
6.1 学习 182
6.2 线性分类器、感知器算法、边缘 184
6.3 非线性分类器、支持向量机、核 189
6.4 强与弱学习-推进 194
6.5 预测中所需样本个数：VC维 196
6.6 Vapnik-Chervonenkis（VC）维 199
6.6.1 集合系统及其VC维实例 199
6.6.2 粉碎函数 202
6.6.3 有界VC维集合系统的粉碎函数 203
6.6.4 交集系统 205
6.7 VC定理 206
文献注记 210
练习 210
第7章 海量数据问题的算法 216
7.1 数据流的频数距 216
7.1.1 在一个数据流中不同元素的个数 217
7.1.2 计算给定元素出现的次数 222
7.1.3 统计高频元素 222
7.1.4 二阶矩 224
7.2 大矩阵概要 228
7.2.1 利用抽样的矩阵乘法 229
7.2.2 利用行和列的取样近似矩阵 232
7.3 文件概要 234
练习 236
第8章 聚类 240
8.1 若干聚类的例子 240
8.2 一个简单的k聚类贪婪算法 242
8.3 k均值聚类的Lloyd算法 243
8.4 通过奇异值分解的有意义聚类 246
8.5 基于稀疏削减的递归聚类 251
8.6 核方法 255
8.7 凝聚聚类 257
8.8 社区，密集的子矩阵 259
8.9 流方法 262
8.10 线性规划 265
8.11 不检查全图地寻找本地群集 266
8.12 聚类公理 271
8.12.1 不可能的结果 272
8.12.2 可满足集公理 277
练习 279
第9章 图模型和信念传播 283
9.1 贝叶斯网络（信念网络） 284
9.2 马尔可夫随机场 285
9.3 因子图 286
9.4 树算法 286
9.5 消息传递算法 289
9.6 单环图 290
9.7 单回路网络的信念更新 291
9.8 最大权重匹配 293
9.9 警告传播 296
9.10 变量之间的相关性 297
练习 301
第10章 其他主题 302
10.1 排名 302
10.2 野兔投票系统 305
10.3 压缩传感和稀疏向量 306
10.3.1 稀疏向量的唯一重建 307
10.3.2 精确重建性 308
10.3.3 受限的等距属性 309
10.4 应用 312
10.4.1 在一些坐标基下的稀疏向量 312
10.4.2 一种表示方法不可能在时域和频域上同时稀疏 312
10.4.3 生物 315
10.4.4 寻找重叠团或团体 316
10.4.5 低秩矩阵 316
练习 317
附录 320
附录1 渐近符号 320
附录2 有用的不等式 321
附录3 级数求和 328
附录4 概率 333
附录5 母函数 350
附录6 特征值与特征向量 356
附录7 其他内容 371
练习 376
参考文献 382
索引 386