Convex Optimization & Euclidean Distance Geometry

front cover......Page 1
binding......Page 2
title......Page 3
© copyright......Page 4
Prelude......Page 7
Contents......Page 9
List of Figures......Page 13
List of Tables......Page 19
1 Overview......Page 21
2 Convex geometry......Page 35
2.1 Convex set......Page 36
2.2 Vectorized-matrix inner product......Page 50
2.3 Hulls......Page 61
2.4 Halfspace, Hyperplane......Page 70
2.5 Subspace representations......Page 84
2.6 Extreme, Exposed......Page 91
2.7 Cones......Page 95
2.8 Cone boundary......Page 104
2.9 Positive semidefinite (PSD) cone......Page 112
2.10 Conic independence (c.i.)......Page 140
2.12 Convex polyhedra......Page 146
2.13 Dual cone & generalized inequality......Page 155
3 Geometry of convex functions......Page 217
3.1 Convex function......Page 218
3.2 Practical norm functions, absolute value......Page 223
3.3 Inverted functions and roots......Page 233
3.4 Affine function......Page 235
3.5 Epigraph, Sublevel set......Page 239
3.6 Gradient......Page 248
3.7 Convex matrix-valued function......Page 260
3.8 Quasiconvex......Page 267
3.9 Salient properties......Page 269
4 Semidefinite programming......Page 271
4.1 Conic problem......Page 272
4.2 Framework......Page 282
4.3 Rank reduction......Page 297
4.4 Rank-constrained semidefinite program......Page 306
4.5 Constraining cardinality......Page 331
4.6 Cardinality and rank constraint examples......Page 351
4.7 Constraining rank of indefinite matrices......Page 398
4.8 Convex Iteration rank-1......Page 404
5 Euclidean Distance Matrix......Page 409
5.1 EDM......Page 410
5.3  fifth Euclidean metric property......Page 411
5.4 EDM definition......Page 416
5.5 Invariance......Page 449
5.6 Injectivity of D & unique reconstruction......Page 454
5.7 Embedding in affine hull......Page 460
5.8 Euclidean metric versus matrix criteria......Page 465
5.9 Bridge: Convex polyhedra to EDMs......Page 473
5.10 EDM-entry composition......Page 480
5.11 EDM indefiniteness......Page 483
5.12 List reconstruction......Page 491
5.13 Reconstruction examples......Page 495
5.14 Fifth property of Euclidean metric......Page 501
6 Cone of distance matrices......Page 511
6.1 Defining EDM cone......Page 513
6.2 Polyhedral bounds......Page 515
6.3 EDM cone is not convex......Page 516
6.4 EDM definition in 11T......Page 517
6.5 Correspondence to PSD cone S+N-1......Page 525
6.6 Vectorization & projection interpretation......Page 531
6.7 A geometry of completion......Page 536
6.8 Dual EDM cone......Page 543
6.9 Theorem of the alternative......Page 557
6.10 Postscript......Page 559
7 Proximity problems......Page 561
7.1 First prevalent problem:......Page 569
7.2 Second prevalent problem:......Page 580
7.3 Third prevalent problem:......Page 592
7.4 Conclusion......Page 602
A.1 Main-diagonal  operator, , tr, vec......Page 605
A.2 Semidefiniteness: domain of test......Page 610
A.3 Proper statements......Page 613
A.4 Schur complement......Page 625
A.5 Eigenvalue decomposition......Page 630
A.6 Singular value decomposition, SVD......Page 634
A.7 Zeros......Page 639
B Simple matrices......Page 647
B.1 Rank-one matrix (dyad)......Page 648
B.2 Doublet......Page 653
B.3 Elementary matrix......Page 654
B.4 Auxiliary V-matrices......Page 656
B.5 Orthomatrices......Page 661
C.1 Properties of infima......Page 667
C.2 Trace, singular and eigen values......Page 668
C.3 Orthogonal Procrustes problem......Page 675
C.4 Two-sided orthogonal Procrustes......Page 677
C.5 Nonconvex quadratics......Page 682
D.1 Directional derivative, Taylor series......Page 683
D.2 Tables of gradients and derivatives......Page 704
E Projection......Page 713
E.1 Idempotent matrices......Page 717
E.2 I---P, Projection on algebraic complement......Page 722
E.3 Symmetric idempotent matrices......Page 723
E.4 Algebra of projection on affine subsets......Page 729
E.5 Projection examples......Page 730
E.6 Vectorization interpretation,......Page 736
E.7 Projection on matrix subspaces......Page 744
E.8 Range/Rowspace interpretation......Page 747
E.9 Projection on convex set......Page 748
E.10 Alternating projection......Page 762
F Notation, Definitions, Glossary......Page 783
Bibliography......Page 803
Index......Page 833
back cover......Page 868