Linear Algebra - Matrix Vector (Multiplication)

> Linear Algebra

1 - About

There is two ways to multiply a matrix by a vector:

  • matrix vector
  • or vector matrix

For each of these multiplication, two equivalent implementations (definitions):

Advertising

3 - Definition

3.1 - Ordinary

“Ordinary” Definition of Matrix-Vector Multiplication: If M is an R x C matrix and u is a C-vector then M * u is the R-vector v such that, for each <math>r \in \mathbb{R}</math>.

<MATH> v[r] = \sum_{k \in C} (M[r,c]u[c]) </MATH>

3.2 - Algebraic properties

Let A be an R x C matrix:

  • For any C-vector v and any scalar <math>\alpha</math>,

<MATH> A*( \alpha v) = \alpha ( A * v) </MATH>

  • For any C-vector u and v:

<MATH> A*( u + v) = A * u + A * v </MATH>

4 - Type

4.1 - Linear Combination

Linear Combination definitions for a matrix-vector multiplication with a matrix M (RxC).

If the vector is a:

  • C-vector (If v is not a C-vector then error)

<MATH> M * v_c = \sum_{c \in C} ( v[c]*(columnVector_c \text{ of } M )) </MATH>

<MATH> \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [7,0,4] = 7 * [1,10] + 0 * [2,20] + 4 * [3,30] </MATH>

  • R-vector

<MATH> v_r * M = \sum_{r \in R} ( v_r[r]*(rowVector_r \text{ of } M)) </MATH>

<MATH> [7,4] * \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} = 7 * [1,2,3] + 4 * [10,20,30] </MATH>

  • Others (???)

<MATH> \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [1,0.5,2] = \begin{pmatrix} 8 \\ 75 \end{pmatrix} </MATH>

Advertising

4.1.1 - Application

Fundamental Computational Problem: Solving a linear matrix-vector equation

  • input: an R x C matrix A and an R-vector b
  • output: the C-vector x such that A * x = b

Problem:

  • Simple formula to solve:

<math>\begin{bmatrix}a & c \\ b & d \end{bmatrix} * \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}p \\ q \end{bmatrix}</math>

  • Solution:

<math>\text{if } ad \neq bc: x = \frac{\displaystyle dp - cq}{\displaystyle ad - bc} \text{ and } y = \frac{\displaystyle aq - bp}{\displaystyle ad - bc}</math>

A algorithm for solving a matrix-vector equation can be use to solve a vector-matrix equation, using transpose.

4.2 - Dot Product

The Dot Product Definition of matrix-vector multiplication is the multiplication of two vectors applied in batch to the row of the matrix.

Let M be an R x C matrix, M * u is the R-vector v such that v[r] is the dot-product of row r of M with u. <MATH>v = [\text{for each } r \in R: v[r] = (row_r \text{ of } M) * u]</MATH>

Example: <MATH> \begin{array}{rcl} \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 10 & 0 \end{bmatrix} * [3,-1] & = & [ [1, 2].[3,-1], [3, 4].[3,-1], [10, 0].[3,-1] ] \\ & = & [ 1,5,30 ] \end{array} </MATH>

Advertising

4.2.1 - Applications of dot-product

  • Downsampling: Each pixel of the low-res image corresponds to a little grid of pixels of the high-res image. The intensity value of a low-res pixel is the average of the intensity values of the corresponding high-res pixels. Averaging can be expressed as dot-product. We want to compute a dot-product for each low-res pixel. Can be expressed as matrix-vector multiplication.
  • blurring: To blur a face, replace each pixel in face with average of pixel intensities in its neighborhood. Average can be expressed as dot-product. By dot-product definition of matrix-vector multiplication, can express this image transformation as a matrix-vector product. Gaussian blur: a kind of weighted average
  • Audio search: Lots of dot-products, Represent as a matrix-vector product, One row per dot-product. To search for [0,1,-1] in in [0, 0,−1, 2, 3,−1, 0, 1,−1,−1]:

<MATH> \begin{bmatrix} \begin{array}{rrr} 0 & 0 & -1 \\ 0 & -1 & 2 \\ -1 & 2 & 3 \\ 2 & 3 & -1 \\ 3 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & -1 \end{array} \end{bmatrix} * [0,1,-1] </MATH>

5 - Computation

To compute matrix-vector or vector-matrix product, we could use dot-product or linear-combinations definition. However, using those definitions, it’s not easy to exploit sparsity in the matrix.

  • Without using sparsity

for i in R:

<math>v[i] := \sum_{j \in C} M[i,j]u[j]</math>

  • Using sparsity in the matrix
initialize v to zero vector
for each pair (i , j) in sparse representation,
    v[i] = v[i] + M[i,j] u[j]
linear_algebra/matrix_vector.txt · Last modified: 2013/08/20 22:07 by gerardnico