017_LAlgIntro(Scala)
Import Notebook

Archived YouTube video of this live unedited lab-lecture:

Archived YouTube video of this live unedited lab-lecture Archived YouTube video of this live unedited lab-lecture

Linear Algebra Review / re-Introduction

by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

This is a breeze'y scalarific break-down of:

Using the above resources we'll provide a review of basic linear algebra concepts that will recur throughout the course. These concepts include:

  1. Matrices
  2. Vectors
  3. Arithmetic operations with vectors and matrices

We will see the accompanying Scala computations in the local or non-distributed setting.

Let's get a quick visual geometric interpretation for vectors, matrices and matrix-vector multiplications, eigen systems with real and comples Eigen values NOW from the following interactive visual-cognitive aid at:

Matrix by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

(watch now 0-61 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

Breeze is a linear algebra package in Scala. First, let us import it as follows:

import breeze.linalg._
import breeze.linalg._

1. Matrix: creation and element-access

A matrix is a two-dimensional array.

Let us denote matrices via bold uppercase letters as follows:

For instance, the matrix below is denoted with A\mathbf{A}, a capital bold A.

A=(a11a12a13a21a22a23a31a32a33) \mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

We usually put commas between the row and column indexing sub-scripts, to make the possibly multi-digit indices distinguishable as follows:

A=(a1,1a1,2a1,3a2,1a2,2a2,3a3,1a3,2a3,3) \mathbf{A} = \begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{pmatrix}

  • Ai,j \mathbf{A}_{i,j} denotes the entry in ii-th row and jj-th column of the matrix A\mathbf{A}.
  • So for instance,
    • the first entry, the top left entry, is denoted by A1,1 \mathbf{A}_{1,1} .
    • And the entry in the third row and second column is denoted by A3,2 \mathbf{A}_{3,2} .
    • We say that a matrix with n rows and m columns is an nn by mm matrix and written as n×mn \times m
      • The matrix A\mathbf{A} shown above is a generic 3×33 \times 3 (pronounced 3-by-3) matrix.
      • And the matrix in Ameet's example in the video above, having 4 rows and 3 columns, is a 4 by 3 matrix.
    • If a matrix A\mathbf{A} is n×mn \times m , we write:
      • A∈Rn×m\mathbf{A} \in \mathbb{R}^{n \times m} and say that A\mathbf{A} is an R\mathbb{R} to the power of the n times m,
        • where, R\mathbb{R} here denotes the set of all real numbers in the line given by the open interval: (−∞,+∞) (-\infty,+\infty).

Let us created a matrix A as a val (that is immutable) in scala. The matrix we want to create is mathematically notated as follows:

A=(a1,1a1,2a1,3a2,1a2,2a2,3)=(123456) \mathbf{A} = \begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} 

val A = DenseMatrix((1, 2, 3), (4, 5, 6)) // let's create this 2 by 3 matrix
A: breeze.linalg.DenseMatrix[Int] = 1 2 3 4 5 6 
A.size
res0: Int = 6 
A.rows // number of rows
res1: Int = 2 
A.size / A.rows // num of columns
res2: Int = 3 
A.cols // also say
res3: Int = 3

Now, let's access the element a1,1a_{1,1}, i.e., the element from the first row and first column of A\mathbf{A}, which in our val A matrix is the integer of type Int equalling 1.

A(0, 0) // Remember elements are indexed by zero in scala
res4: Int = 1

Gotcha: indices in breeze matrices start at 0 as in numpy of python and not at 1 as in MATLAB!

Of course if you assign the same dense matrix to a mutable var B then its entries can be modified as follows:

var B = DenseMatrix((1, 2, 3), (4, 5, 6))
B: breeze.linalg.DenseMatrix[Int] = 1 2 3 4 5 6 
B(0,0)=999; B(1,1)=969; B(0,2)=666
B
res5: breeze.linalg.DenseMatrix[Int] = 999 2 666 4 969 6

Vector

(watch now 0:31 = 62-93 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

  • A vector is a matrix with many rows and one column.

  • We'll denote a vector by bold lowercase letters: a=(3.31.06.33.6)\mathbf{a} = \begin{pmatrix} 3.3 \\ 1.0 \\ 6.3 \\ 3.6 \end{pmatrix}

    So, the vector above is denoted by a\mathbf{a}, the lowercase, bold a.

  • aia_i denotes the i-th entry of a vector. So for instance:
    • a2a_2 denotes the second entry of the vector and it is 1.0 for our vector.
  • If a vector is m-dimensional, then we say that a\mathbf{a} is in Rm\mathbb{R}^m and write a∈ Rm\mathbf{a} \in \ \mathbb{R}^m.
    • So our a∈ R4\mathbf{a} \in \ \mathbb{R}^4.
val a = DenseVector(3.3, 1.0, 6.3, 3.6) // these are row vectors
a: breeze.linalg.DenseVector[Double] = DenseVector(3.3, 1.0, 6.3, 3.6) 
a.size // a is a column vector of size 4
res6: Int = 4 
a(1) // the second element of a is indexed by 1 as the first element is indexed by 0
res7: Double = 1.0 
val a = DenseVector[Double](5, 4, -1) // this makes a vector of Doubles from input Int
a: breeze.linalg.DenseVector[Double] = DenseVector(5.0, 4.0, -1.0) 
val a = DenseVector(5.0, 4.0, -1.0) // this makes a vector of Doubles from type inference . NOTE "5.0" is needed not just "5."
a: breeze.linalg.DenseVector[Double] = DenseVector(5.0, 4.0, -1.0) 
val x = DenseVector.zeros[Double](5) // this will output x: breeze.linalg.DenseVector[Double] = DenseVector(0.0, 0.0, 0.0, 0.0, 0.0)
x: breeze.linalg.DenseVector[Double] = DenseVector(0.0, 0.0, 0.0, 0.0, 0.0)

Transpose

(watch now 1:02 = 95-157 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

Suggested Home Work for the linear-algebraically rusty (LiAlRusty): watch again and take notes.

val A = DenseMatrix((1, 4), (6, 1), (3, 5)) // let's create this 2 by 3 matrix
A: breeze.linalg.DenseMatrix[Int] = 1 4 6 1 3 5 
A.t // transpose of A
res8: breeze.linalg.DenseMatrix[Int] = 1 6 3 4 1 5 
val a = DenseVector(3.0, 4.0, 1.0)
a: breeze.linalg.DenseVector[Double] = DenseVector(3.0, 4.0, 1.0) 
a.t
res9: breeze.linalg.Transpose[breeze.linalg.DenseVector[Double]] = Transpose(DenseVector(3.0, 4.0, 1.0))

Addition and Subtraction

(watch now 0:59 = 157-216 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

Suggested Home Work for LiAlRusty: watch again and take notes.

Pop Quiz:

  • what is a natural geometric interpretation of vector addition, subtraction, matric addition and subtraction?
val A = DenseMatrix((1, 4), (6, 1), (3, 5))
A: breeze.linalg.DenseMatrix[Int] = 1 4 6 1 3 5 
val B = -A
B: breeze.linalg.DenseMatrix[Int] = -1 -4 -6 -1 -3 -5 
A + B // should be A-A=0
res10: breeze.linalg.DenseMatrix[Int] = 0 0 0 0 0 0 
A - B // should be A+A=2A
res11: breeze.linalg.DenseMatrix[Int] = 2 8 12 2 6 10 
B - A // should be -A-A=-2A
res13: breeze.linalg.DenseMatrix[Int] = -2 -8 -12 -2 -6 -10

Operators

All Tensors support a set of operators, similar to those used in Matlab or Numpy.

For HOMEWORK see: Workspace -> scalable-data-science -> xtraResources -> LinearAlgebra -> LAlgCheatSheet for a list of most of the operators and various operations.

Some of the basic ones are reproduced here, to give you an idea.

Operation Breeze Matlab Numpy
Elementwise addition a + b a + b a + b
Elementwise multiplication a :* b a .* b a * b
Elementwise comparison a :< b a < b (gives matrix of 1/0 instead of true/false) a < b
Inplace addition a :+= 1.0 a += 1 a += 1
Inplace elementwise multiplication a :*= 2.0 a *= 2 a *= 2
Vector dot product a dot b,a.t * b† dot(a,b) dot(a,b)
Elementwise sum sum(a) sum(sum(a)) a.sum()
Elementwise max a.max max(a) a.max()
Elementwise argmax argmax(a) argmax(a) a.argmax()
Ceiling ceil(a) ceil(a) ceil(a)
Floor floor(a) floor(a) floor(a)

Scalar multiplication, Dot Product and Matrix-Vector multiplication

(watch now 2:26 = 218-377 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

Suggested Home Work for LiAlRusty: watch again and take notes.

Pop Quiz:

  • what is a natural geometric interpretation of scalar multiplication of a vector or a matrix and what about vector matrix multiplication?

    Let's get a quick visual geometric interpretation for vectors, matrices and matrix-vector multiplications from the first interactive visual-cognitive aid at:

val A = DenseMatrix((1, 4), (6, 1), (3, 5))
A: breeze.linalg.DenseMatrix[Int] = 1 4 6 1 3 5 
5 * A
res15: breeze.linalg.DenseMatrix[Int] = 5 20 30 5 15 25 
A * 5
res16: breeze.linalg.DenseMatrix[Int] = 5 20 30 5 15 25

Dot product

val A = DenseMatrix((1, 4), (6, 1), (3, 5))
A: breeze.linalg.DenseMatrix[Int] = 1 4 6 1 3 5 
val B = DenseMatrix((3, 1), (2, 2), (1, 3))
B: breeze.linalg.DenseMatrix[Int] = 3 1 2 2 1 3 
A *:* B // element-wise multiplication
res17: breeze.linalg.DenseMatrix[Int] = 3 4 12 2 3 15

Matrix Vector multiplication

val A = DenseMatrix((1, 4), (3, 1))
A: breeze.linalg.DenseMatrix[Int] = 1 4 3 1 
val a = DenseVector(1, -1) // is a column vector
a: breeze.linalg.DenseVector[Int] = DenseVector(1, -1) 
a.size // a is a column vector of size 2
res18: Int = 2 
A * a
res19: breeze.linalg.DenseVector[Int] = DenseVector(-3, 2)

Matrix-Matrix multiplication

(watch now 1:59 = 380-499 seconds):

Linear Algebra Review by Ameet Talwalkar in BerkeleyX: CS190.1x Scalable Machine Learning

val A = DenseMatrix((1,2,3),(1,1,1))
A: breeze.linalg.DenseMatrix[Int] = 1 2 3 1 1 1 
val B = DenseMatrix((4, 1), (9, 2), (8, 9))
B: breeze.linalg.DenseMatrix[Int] = 4 1 9 2 8 9 
A*B // 4+18+14
res20: breeze.linalg.DenseMatrix[Int] = 46 32 21 12