Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
The Random Projection Method
 
Santosh S. Vempala Massachusetts Institute of Technology, Cambridge, MA
A co-publication of the AMS and DIMACS
The Random Projection Method
Softcover ISBN:  978-0-8218-3793-1
Product Code:  DIMACS/65.S
List Price: $52.00
MAA Member Price: $46.80
AMS Member Price: $41.60
eBook ISBN:  978-1-4704-1777-2
Product Code:  DIMACS/65.E
List Price: $49.00
MAA Member Price: $44.10
AMS Member Price: $39.20
Softcover ISBN:  978-0-8218-3793-1
eBook: ISBN:  978-1-4704-1777-2
Product Code:  DIMACS/65.S.B
List Price: $101.00 $76.50
MAA Member Price: $90.90 $68.85
AMS Member Price: $80.80 $61.20
The Random Projection Method
Click above image for expanded view
The Random Projection Method
Santosh S. Vempala Massachusetts Institute of Technology, Cambridge, MA
A co-publication of the AMS and DIMACS
Softcover ISBN:  978-0-8218-3793-1
Product Code:  DIMACS/65.S
List Price: $52.00
MAA Member Price: $46.80
AMS Member Price: $41.60
eBook ISBN:  978-1-4704-1777-2
Product Code:  DIMACS/65.E
List Price: $49.00
MAA Member Price: $44.10
AMS Member Price: $39.20
Softcover ISBN:  978-0-8218-3793-1
eBook ISBN:  978-1-4704-1777-2
Product Code:  DIMACS/65.S.B
List Price: $101.00 $76.50
MAA Member Price: $90.90 $68.85
AMS Member Price: $80.80 $61.20
  • Book Details
     
     
    DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
    Volume: 652004; 105 pp
    MSC: Primary 68; 90;

    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.

    Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

    Readership

    Graduate students and research mathematicians interested in computational geometry.

  • Table of Contents
     
     
    • Chapters
    • Random projection
    • Combinatorial optimization
    • Rounding via random projection
    • Embedding metrics in Euclidean space
    • Euclidean embeddings: Beyond distance preservation
    • Learning theory
    • Robust concepts
    • Intersections of half-spaces
    • Information retrieval
    • Nearest neighbors
    • Indexing and clustering
  • Additional Material
     
     
  • Reviews
     
     
    • The book offers a broad view of its subject, with a good selection of examples and a vast set of bibliographic references. It could be used well as a starting point for research in this area. The presence of a number of exercises [also] makes it a possible choice for [a] textbook on this method.

      Mathematical Reviews
    • A very nice piece of work — the author succeeds in tying together a lot of recent developments in algorithms under an appealing theme.

      Professor Jon Kleinberg, Cornell University
    • This is an elegant monograph, dense in ideas and techniques, diverse in its applications, and above all, vibrant with the author's enthusiasm for the area.

      from the Foreword by Christos H. Papadimitriou, University of California, Berkeley
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 652004; 105 pp
MSC: Primary 68; 90;

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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

Readership

Graduate students and research mathematicians interested in computational geometry.

  • Chapters
  • Random projection
  • Combinatorial optimization
  • Rounding via random projection
  • Embedding metrics in Euclidean space
  • Euclidean embeddings: Beyond distance preservation
  • Learning theory
  • Robust concepts
  • Intersections of half-spaces
  • Information retrieval
  • Nearest neighbors
  • Indexing and clustering
  • The book offers a broad view of its subject, with a good selection of examples and a vast set of bibliographic references. It could be used well as a starting point for research in this area. The presence of a number of exercises [also] makes it a possible choice for [a] textbook on this method.

    Mathematical Reviews
  • A very nice piece of work — the author succeeds in tying together a lot of recent developments in algorithms under an appealing theme.

    Professor Jon Kleinberg, Cornell University
  • This is an elegant monograph, dense in ideas and techniques, diverse in its applications, and above all, vibrant with the author's enthusiasm for the area.

    from the Foreword by Christos H. Papadimitriou, University of California, Berkeley
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.