HW1 for CS 6210

You may (and probably should) talk about problems with the each other, with the TA, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.

md"""

# HW1 for CS 6210

You may (and probably should) talk about problems with the each other, with the TA, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.

"""

214 μs

using LinearAlgebra

262 μs

1. All about you

How do you prefer to be called?
Why are you taking the class?
Are there things you particularly hope to learn?
Do you have any concerns (about background, schedule, etc)?
Is there anything else I should know about your situation?

md"""

## 1. All about you

- How do you prefer to be called?

- Why are you taking the class?

- Are there things you particularly hope to learn?

- Do you have any concerns (about background, schedule, etc)?

- Is there anything else I should know about your situation?

"""

1.4 ms

2. A little differentiation

Differentiate $\|Ax\|^2$ with respect to $x$ and $A$, and write the result in the form

$$\delta[ \|Ax\|^2 ] = g^T \delta x + \langle G, \delta A \rangle_F$$

You may use the following tester as a sanity check.

md"""

## 2. A little differentiation

Differentiate $\|Ax\|^2$ with respect to $x$ and $A$, and write the result in the form

$$\delta[ \|Ax\|^2 ] = g^T \delta x + \langle G, \delta A \rangle_F$$

You may use the following tester as a sanity check.

"""

218 μs

check_p2 (generic function with 2 methods)

function check_p2(A, x, G, g, h = 1e-4)

# Pick a random direction

δA = rand(size(A)...)

δx = rand(size(x)...)

# Compute an estimated directional derivative by finite differences

np = norm((A+h*δA)*(x+h*δx))^2

nm = norm((A-h*δA)*(x-h*δx))^2

dn_fd = (np-nm)/(2*h)

# Compute the analytical directional derivative

dn_analytical = dot(g, δx) + dot(G, δA)

# Return the relative error between the two computations

abs((dn_fd-dn_analytical)/dn_fd)

end

929 μs

3: Norm!

For $A = xy^T$, verify the following

$$\|A\|_1 = \|x\|_1 \|y\|_\infty$$
$$\|A\|_\infty = \|x\|_\infty \|y\|_1$$
$$\|A\|_F = \|x\|_2 \|y\|_2$$
$$\|A\|_2 = \|x\|_2 \|y\|_2$$

md"""

## 3: Norm!

For $A = xy^T$, verify the following

- $\|A\|_1 = \|x\|_1 \|y\|_\infty$

- $\|A\|_\infty = \|x\|_\infty \|y\|_1$

- $\|A\|_F = \|x\|_2 \|y\|_2$

- $\|A\|_2 = \|x\|_2 \|y\|_2$

"""

254 μs

4: Seeking structure

Suppose $A = I + uv^T$ for $u, v \in \mathbb{R}^n$. Rewrite each of the computations in the following code to take $O(n)$ time:

md"""

## 4: Seeking structure

Suppose $A = I + uv^T$ for $u, v \in \mathbb{R}^n$. Rewrite each of the computations in the following code to take $O(n)$ time:

"""

151 μs

1242.0657597962686

let

n = 1000 # Change this to 10000 as a sanity check!

u = rand(n)

v = rand(n)

x = rand(n)

# Reference computations

A = I + u*v'

y1 = A*x # Part 1

y2 = A'*x # Part 2

d = diag(A) # Part 3

t = tr(A) # Part 4

end

2.9 ms