Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Matrix Computations: Low Rank Approximation

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

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.

Matrix decomposition

In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of problems. In numerical analysis, different decompositions are used to implement efficient matrix algorithms. For instance, when solving a system of linear equations , the matrix A can be decomposed via the LU decomposition.

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).

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.

Related lectures (44)

Matrix Multiplication: Algorithms and Complexity

Covers matrix notation, arithmetic, multiplication, algorithms, and complexity of matrix multiplication.

Solving Parity Games in Practice

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

SVD: Singular Value Decomposition

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

Matrix-Matrix Multiplication: Algorithms and Applications

Explores theoretical and practical aspects of fast matrix-matrix multiplication algorithms and their significance in computer science.

Dynamic Programming: Rod Cutting and Matrix Chain Multiplication