电子书《Sketching Algorithms》草图算法
www.sketchingbigdata.org/fall20/lec/notes.pdf
作者Jelani Osei Nelson 是加州大学伯克利分校电气工程和计算机科学系的教授。
本书涵盖了草图算法（Sketching Algorithms）在大数据处理中的应用。草图算法是一种通过压缩数据集来高效计算或近似计算某些函数的技术。文章详细介绍了多种草图算法，包括计数问题（如近似计数、不同元素计数和分位数查询）、线性草图（如重击者检测和图草图）、Johnson-Lindenstrauss变换、线性代数应用（如矩阵乘法、最小二乘回归和低秩近似）以及压缩感知等。每种算法都通过理论分析和实际应用展示了其在处理大规模数据时的高效性和准确性。文章还讨论了草图算法的下界证明方法，包括基于压缩和通信复杂性的证明技巧。
