Linear Algebra Tools For Data Mining 2E – Dan A Simovici

Indeed, for u, v ∈Rn, we have cos ∠(ha(u), ha(v)) = ha(u)′ha(v)) ∥ha(u)∥2∥ha(v)∥2 = u′v ∥u∥2∥v∥2 = cos ∠(u, v). The set of dilations having a non-zero ratio is easily seen to be a group, where (ha)−1 = h 1 a . 6.18 Condition Numbers for Matrices Let Au = b be a linear system, where A ∈Cn×n is a non-singular matrix and b ∈Rn. We examine the sensitivity of the solution of this system to small variations of b.

So, together with the original system, we work with a system of the form Av = b + h, where h ∈Rn is the perturbation of b. Note that A(v −u) = h, so v −u = A−1b. Using a vector norm ∥· ∥and its corresponding matrix norm ||| · |||, we have ∥v −u∥= ∥A−1h∥⩽|||A−1|||∥h∥. Since ∥b∥= ∥Au∥⩽|||A|||∥u∥, it follows that ∥v −u∥ ∥u∥ ⩽|||A−1|||∥h∥ ∥b∥ = |||A||||||A−1|||∥h∥ ∥b∥ . (6.33) Thus, the relative variation of the solution, ∥v−u∥ ∥u∥, is upper bounded by the number |||A||||||A−1|||∥h∥ ∥b∥ .

These considerations justify the follow- ing definition. Definition 6.34. Let A ∈Cn×n be a non-singular matrix. The con- dition number of A relative to the matrix norm ||| · ||| is the number cond(A) = |||A||||||A−1|||. Equality (6.33) implies that if the condition number is large, then small variations in b may generate large variations in the solution of the system Au = b, especially when b is close to 0.

When this is the Norms and Inner Products case, we say that the system Au = b is ill-conditioned. Otherwise, the system Au = b is well-conditioned. Theorem 6.72. Let A ∈Cn×n be a non-singular matrix. The fol- lowing statements hold for every matrix norm induced by a vector norm: (i) cond(A) = cond(A−1); (ii) cond(cA) = |c|cond(A); (iii) cond(A) ⩾1. Proof. We prove here only Part (iii). Since AA−1 = I, by the properties of a matrix norm induced by a vector norm, we have cond(A) = |||A||||||A−1||| ⩾|||AA−1||| = |||In||| = 1.

□ Let A, B be two non-singular matrices in Cn×n such that B = aA, where a ∈C. We have B−1 = aA−1, |||B||| = |a||||B|||, and |||B−1||| = |a||||A−1||| so cond(B) = |a|2cond(A). On the other hand, det(B) = an det(A).

This page intentionally left blank This page intentionally left blank This page intentionally left blank This page intentionally left blank Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE Library of Congress Cataloging-in-Publication Data Names: Simovici, Dan A., author.

Title: Linear algebra tools for data mining / Dan A. Simovici, University of Massachusetts Boston, USA, Dana-Farber Cancer Institute, USA. Description: Second edition. | New Jersey : World Scientific Publishing Co. Pte. Ltd., [2023] | Includes bibliographical references and index. Identifiers: LCCN 2022062233 | ISBN 9789811270338 (hardcover) | ISBN 9789811270345 (ebook for institutions) | ISBN 9789811270352 (ebook for individuals) Subjects: LCSH: Data mining. | Parallel processing (Electronic computers) | Computer algorithms.

| Linear programming. Classification: LCC QA76.9.D343 S5947 2023 | DDC 006.3/12–dc23/eng/20230210 LC record available at https://lccn.loc.gov/2022062233 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. Copyright © 2023 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. For any available supplementary material, please visit https://www.worldscientific.com/worldscibooks/10.1142/13248#t=suppl Desk Editors: Balasubramanian/Steven Patt Typeset by Stallion Press Email: [email protected] Printed in Singapore To my wife, Doina, and to the memory of my brother, Dr. George Simovici This page intentionally left blank This page intentionally left blank This page intentionally left blank This page intentionally left blank Preface Linear algebra plays an increasingly important role in data mining and pattern recognition research either directly, or through the appli- cations of linear algebra in graph theory and optimization.

Linear algebra-based algorithms are elegant and fast, are based on a common mathematical doctrine with its collection of basic ideas and techniques, and are easy to implement; they are especially suit- able for parallel and distributed computation to approach large-scale challenging problems such as searching and extracting patterns from the entire web. Thus, the application of linear algebra-based tech- niques in data mining and machine learning research constitute an increasingly attractive area. Many linear algebra results are impor- tant for their applications in biology, chemistry, psychology, and sociology.

The standard undergraduate education of a computer scientist includes one or, rarely, two semesters of linear algebra, which is woefully inadequate for a researcher in data mining or pattern recog- nition.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 50528ad1a90fffcc
• File Extension: .pdf
• File Size: 11,138,154 bytes (10.622 MB)
• Title: –
• Author: Unknown
• ISBN: 9789811270338, 9789811270345, 9789811270352
• Pages: 1003
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1399.38 minutes
• Total Words: 279,875
• Total Characters: 1,295,420
• Average Words per Page: 279.04
• Average Characters per Page: 1291.55

Most Frequent Words

matrix (2879), let (2069), linear (1314), theorem (989), matrices (928), set (702), prove (674), data (661), second (643), rank (632), proof (611), algebra (596), two (553), since (549), mining (526), implies (498), tools (493), edition (491), space (474), every (466), det (459), thus (447), example (446), follows (395), function (394), vectors (372), defined (365), definition (361), solution (354), vector (353), basis (347), number (340), product (332), form (328), exists (327), equality (326), columns (321), suppose (320), therefore (318), dim (318), trace (280), positive (279), spec (264), note (263), first (261), eigenvalues (250), subspace (250), diagonal (248), real (240), write (240), spaces (238), norm (238), values (233), elements (221), corollary (217), given (215), numbers (211), system (208), singular (207), unitary (205), mapping (205), range (204), tensor (202), hermitian (193), define (193), max (190), following (184), using (182), linearly (180), also (178), column (176), written (175), row (175), sequence (175), inner (171), mda (171), orthogonal (169), sum (169), diag (166), eigenvalue (166), null (165), triangular (164), aij (162), array (160), matlab (159), independent (159), norms (156), case (155), components (153), upper (153), symmetric (152), inequality (151), orthonormal (149), invertible (147), tensors (146), decomposition (144), denoted (144), between (142), polynomial (141), equal (141).

PDF Download