Lecture

Matrix Computations: Low Rank Approximation

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture discusses the complexity of matrix computations, focusing on low rank approximation. The instructor explains the problem formulation, the meaning of low rank matrices, and the importance of approximation algorithms. Various algorithms for low rank approximation are explored, including traditional O(n³) methods, powering methods, and randomized algorithms. The lecture covers error measures, matrix norms, and different types of approximation quality. It also delves into sketch and solve algorithms, iterative algorithms, and column subset selection algorithms. Additionally, the lecture touches on other algorithms such as greedy column subset selection, coresets, non-negative matrix factorization, and binary matrix factorization.

Official source

Ontological neighbourhood

Mathematics

Algebra: Linear algebra

Related concepts (32)

Matrix (mathematics)

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object. For example, is a matrix with two rows and three columns. This is often referred to as a "two by three matrix", a " matrix", or a matrix of dimension . Without further specifications, matrices represent linear maps, and allow explicit computations in linear algebra.

Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).

Matrix multiplication

In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.

Sparse matrix

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns. By contrast, if most of the elements are non-zero, the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.

Factorization

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4. Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any can be trivially written as whenever is not zero.

Related lectures (64)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Matrix Multiplication and Divide-and-Conquer Techniques

Discusses matrix multiplication using divide-and-conquer techniques and introduces Strassen's algorithm for improved efficiency.

SVD: Singular Value Decomposition

Covers the concept of Singular Value Decomposition (SVD) for compressing information in matrices and images.

Singular Value Decomposition: Applications and Interpretation

Explains the construction of U, verification of results, and interpretation of SVD in matrix decomposition.

Linear Algebra: Matrices Properties