The Random Projection Method ( DIMACS - Series in Discrete Mathematics and Theoretical Computer Science )

Publication series :DIMACS - Series in Discrete Mathematics and Theoretical Computer Science

Author: Santosh S. Vempala  

Publisher: American Mathematical Society‎

Publication year: 2015

E-ISBN: 9781470417772

P-ISBN(Paperback): 9780821837931

Subject: O241 数值分析

Keyword: 暂无分类

Language: ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

The Random Projection Method

Description

Random projection is a simple geometric technique for reducing the dimensionality of a set of points in Euclidean space while preserving pairwise distances approximately. The technique plays a key role in several breakthrough developments in the field of algorithms. In other cases, it provides elegant alternative proofs. The book begins with an elementary description of the technique and its basic properties. Then it develops the method in the context of applications, which are divided into three groups. The first group consists of combinatorial optimization problems such as maxcut, graph coloring, minimum multicut, graph bandwidth and VLSI layout. Presented in this context is the theory of Euclidean embeddings of graphs. The next group is machine learning problems, specifically, learning intersections of halfspaces and learning large margin hypotheses. The projection method is further refined for the latter application. The last set consists of problems inspired by information retrieval, namely, nearest neighbor search, geometric clustering and efficient low-rank approximation. Motivated by the first two applications, an extension of random projection to the hypercube is developed here. Throughout the book, random projection is used as a way to understand, simplify and connect progress on these important and seemingly unrelated problems. The book is suitable for graduate students and research mathematicians interested in computational geometry.

Chapter

Title page

Contents

Foreword

Acknowledgments

Random projection

Part I. Combinatorial optimization

Rounding via random projection

Embedding metrics in Euclidean space

Euclidean embeddings: Beyond distance preservation

Part II. Learning theory

Robust concepts

Intersections of half-spaces

Part III. Information retrieval

Nearest neighbors

Indexing and clustering

Bibliography

Appendix

Back Cover

The users who browse this book also browse