Linear Algebra Tools For Data Mining

by Dan A Simovici

Overview

This comprehensive volume presents the foundations of linear algebra ideas and techniques applied to data mining and related fields. Linear algebra has gained increasing importance in data mining and pattern recognition, as shown by the many current data mining publications, and has a strong impact in other disciplines like psychology, chemistry, and biology. The basic material is accompanied by more than 550 exercises and supplements, many accompanied with complete solutions and MATLAB applications.

Product Details

ISBN-13:	9789814383493
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	02/01/2012
Pages:	880
Product dimensions:	5.90(w) x 9.10(h) x 2.00(d)

Table of Contents

Preface vii

Part 1 Linear Algebra 1

1 Modules and Linear Spaces 3

1.1 Introduction 3

1.2 Permutations 3

1.3 Groups, Rings, and Fields 8

1.4 Closure and Interior Systems 15

1.5 Modules 20

1.6 Linear Mappings 22

1.7 Submodules 26

1.8 Linear Combinations 31

1.9 The Lattice of Submodules of a Module 32

1.10 Linear Independence 33

1.11 Linear Spaces 35

1.12 Module Isomorphism Theorems 41

1.13 Direct Sums and Direct Products 43

1.14 Dual Modules and Linear Spaces 53

1.15 Topological Linear Spaces 58

Exercises and Supplements 60

Bibliographical Comments 64

2 Matrices 65

2.1 Introduction 65

2.2 Matrices with Arbitrary Elements 65

2.3 Rings and Matrices 68

2.4 Special Classes of Matrices 79

2.5 Complex Matrices 81

2.6 Partitioned Matrices and Matrix Operations 87

2.7 Invertible Matrices 89

2.8 Matrices and Linear Transformations 95

2.9 The Notion of Rank 98

2.10 Matrix Similarity and Congruence 110

2.11 Linear Systems and Matrices 113

2.12 The Row Echelon Form of Matrices 115

2.13 The Kronecker and Hadamard Products 125

2.14 Linear Inequalities 129

2.15 Complex Multilinear Forms 135

Exercises and Supplements 137

Bibliographical Comments 159

3 MATLAB 161

3.1 Introduction 161

3.2 The Interactive Environment of MATLAB 161

3.3 Number Representation and Arithmetic Computations 162

3.4 Matrices Representation 169

3.5 Random Matrices 179

3.6 Control Structures 181

3.7 Indexing 187

3.8 Functions 189

3.9 Matrix Computations 191

Exercises and Supplements 193

Bibliographical Comments 195

4 Determinants 197

4.1 Introduction 197

4.2 Multilinear Forms 197

4.3 Cramer's Formula 214

4.4 Partitioned Matrices and Determinants 215

MATLAB Computations 218

Exercises and Supplements 219

Bibliographical Comments 232

5 Norms on Linear Spaces 233

5.1 Introduction 233

5.2 Fundamental Inequalities 233

5.3 Metric Spaces 236

5.4 Norms 239

5.5 Vector Norms on Rⁿ 241

5.6 The Topology of Normed Linear Spaces 250

5.7 Norms for Matrices 255

5.8 Matrix Sequences and Matrix Series 263

5.9 Condition Numbers for Matrices 267

5.10 Conjugate Norms 269

MATLAB Computations 272

Exercises and Supplements 273

Bibliographical Comments 285

6 Inner Product Spaces 287

6.1 Introduction 287

6.2 Inner Products and Norms 290

6.3 Orthogonality 294

6.4 Hyperplanes in Rⁿ 298

6.5 "Unitary and Orthogonal Matrices 300

6.6 Projection on Subspaces 304

6.7 Positive Definite and Positive Semidennite Matrices 310

6.8 The Gram-Schmidt Orthogonalization Algorithm? 319

6.9 The QR Factorization of Matrices 324

6.10 Matrix Groups 332

MATLAB Computations 334

Exercises and Supplements 338

Bibliographical Comments 349

7 Convexity 351

7.1 Introduction 351

7.2 Convex Sets 351

7.3 Separation of Convex Sets 368

7.4 Cones in Rⁿ 375

7.5 Convex Functions 382

7.6 Convexity and Inequalities 401

7.7 Constrained Extrema and Convexity 406

Exercises and Supplements 415

Bibliographical Comments 427

8 Eigenvalues 429

8.1 Introduction 429

8.2 Eigenvalues and Eigenvectors 429

8.3 The Characteristic Polynomial of a Matrix 434

8.4 Spectra of Special Matrices 441

8.5 Geometry of Eigenvalues 447

8.6 Spectra of Kronecker Products 449

8.7 The Power Method for Eigenvalues 450

8.8 The QR Iterative Algorithm 453

MATLAB Computations 454

Exercises and Supplements 455

Bibliographical Comments 459

9 Similarity and Spectra 461

9.1 Introduction 461

9.2 Diagonalizable Matrices 461

9.3 Matrix Similarity and Spectra 465

9.4 The Sylvester Operator 487

9.5 Geometric versus Algebraic Multiplicity 490

9.6 λ-Matrices 492

9.7 The Jordan Canonical Form 504

9.8 Matrix Norms and Eigenvalues 510

9.9 Matrix Pencils and Generalized Eigenvalues 518

9.10 Quadratic Forms and Quadrics 521

9.11 Spectra of Positive Matrices 530

9.12 Spectra of Positive Semidefmite Matrices 534

9.13 K-Matrices 536

MATLAB Computations 545

Exercises and Supplements 546

Bibliographical Comments 564

10 Singular Values 565

10.1 Introduction 565

10.2 Singular Values and Singular Vectors 565

10.3 Numerical Rank of Matrices 577

10.4 Updating SVDs 580

10.5 Polar Form of Matrices 583

10.6 CS Decomposition 584

10.7 Geometry of Subspaces 588

10.8 Spectral Resolution of a Matrix 594

MATLAB Computations 602

Exercises and Supplements 607

Bibliographical Comments 617

Part 2 Applications 619

11 Graphs and Matrices 621

11.1 Introduction 621

11.2 Graphs 621

11.3 Graph Connectivity 625

11.4 Directed Graphs 635

11.5 Trees 640

11.6 The Adjacency and Incidence Matrices 652

11.7 Operations on Graphs 662

11.8 Digraphs of Matrices 664

MATLAB Computations 668

Exercises and Supplements 671

Bibliographical Comments 677

12 Data Sample Matrices 679

12.1 Introduction 679

12.2 The Sample Matrix 679

12.3 Biplots 688

Exercises and Supplements 694

Bibliographical Comments 695

13 Least Squares Approximation and Data Mining 697

13.1 Introduction 697

13.2 Linear Regression 697

13.3 The Least Square Approximation and QR Decomposition 702

13.4 Partial Least Square Regression 703

13.5 Locally Linear Embedding 705

MATLAB Computations 711

Exercises and Supplements 711

Bibliographical Comments 716

14 Dimensionality Reduction Techniques 717

14.1 Introduction 717

14.2 Principal Component Analysis 717

14.3 Linear Discriminant Analysis 729

14.4 Latent Semantic Indexing 731

14.5 Recommender Systems and SVD 734

14.6 Metric Multidimensional Scaling 737

14.7 Procrustes Analysis 745

14.8 Non-negative Matrix Factorization 751

Exercises and Supplements 758

Bibliographical Comments 765

15 The κ-Means Clustering 769

15.1 Introduction 769

15.2 The κ-Means Algorithm and Convexity 769

15.3 Relaxation of the κ-Means Problem 773

15.4 SVD and Clustering 776

15.5 Evaluation of Clusterings 779

MATLAB Computations 780

Exercises and Supplements 783

Bibliographical Comments 791

16 Spectral Properties of Graphs and Spectral Clustering 793

16.1 Introduction 793

16.2 The Ordinary Spectrum of a Graph 793

16.3 The Laplacian Spectrum of a Graph 796

16.4 Graph Cuts, Separators, and Clusterings 812

16.5 Spectral Clustering Algorithms 827

Exercises and Supplements 834

Bibliographical Comments 842

Bibliography 843

Index 853