Let \(W\) be a walk and let \(u\) be a vertex, what is \(\text{deg}_W(u)\)? (generally)
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
F{a&v[Q@_W
Before
Front
Back
Let \(W\) be a walk and let \(u\) be a vertex, what is \(\text{deg}_W(u)\)? (generally)
it is the degree of \(u\) in \(W\), which is the number of edges incident to \(u\) which are part of \(W\) but repetitions are included, therefore it is possible that \(\text{deg}(u) < \text{deg}_W(u)\)
After
Front
Let \(W\) be a walk and let \(u\) be a vertex, what is \(\text{deg}_W(u)\)? (generally)
Back
Let \(W\) be a walk and let \(u\) be a vertex, what is \(\text{deg}_W(u)\)? (generally)
It is the number of edges incident to \(u\) which are part of \(W\) but repetitions are included, therefore it is possible that \(\text{deg}(u) < \text{deg}_W(u)\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | It is the number of edges incident to \(u\) which are part of \(W\) but <b>repetitions are included</b>, therefore it is possible that \(\text{deg}(u) < \text{deg}_W(u)\). |
Note 2: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
IXC|=r,qdR
Before
Front
The distance \(d(u, v)\) in a directed graph is defined as shortest length of a walk from \(u\) to \(v\)
Back
The distance \(d(u, v)\) in a directed graph is defined as shortest length of a walk from \(u\) to \(v\)
Keep in mind in a weighted graph, this might mean the cheapest, which refers to cost not length.
After
Front
The distance \(d(u, v)\) in a directed graph is defined as shortest length of a walk from \(u\) to \(v\).
Back
The distance \(d(u, v)\) in a directed graph is defined as shortest length of a walk from \(u\) to \(v\).
Keep in mind in a weighted graph, this might mean the cheapest, which refers to cost not length.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The distance \(d(u, v)\) in a directed graph is defined as {{c1:: shortest length of a walk from \(u\) to \(v\)}} | The distance \(d(u, v)\) in a directed graph is defined as {{c1:: shortest length of a walk from \(u\) to \(v\)}}. |
Note 3: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
bS
Before
Front
What does the Handshake lemma say?
Back
What does the Handshake lemma say?
it describes the relationship between the number of vertices and edges in a graph
\(\sum_{v\in V} \text{deg}(v) = 2|E|\)
\(\sum_{v\in V} \text{deg}(v) = 2|E|\)
After
Front
What does the Handshake lemma say?
Back
What does the Handshake lemma say?
It describes the relationship between the number of vertices and edges in a graph:
\(\sum_{v\in V} \text{deg}(v) = 2|E|\)
\(\sum_{v\in V} \text{deg}(v) = 2|E|\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | It describes the relationship between the number of vertices and edges in a graph:<br><br>\(\sum_{v\in V} \text{deg}(v) = 2|E|\) |
Note 4: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
mabS@W|F#G
Before
Front
Explain how to find a topological order (high-level):
Back
Explain how to find a topological order (high-level):
it is a sorting of the vertices of a directed graph, which we can build from the back by always finding a vertex which has no succeeding vertices, remove it from the graph and add it to the front of our topologically sorted list.
This is not possible if there is a directed cycle in the graph.
This is not possible if there is a directed cycle in the graph.
After
Front
Explain how to find a topological order (high-level):
Back
Explain how to find a topological order (high-level):
We can build one backwards, by always finding a vertex which has no succeeding vertices, removing it from the graph and adding it to the front of our topologically sorted list.
This is not possible if there is a directed cycle in the graph.
This is not possible if there is a directed cycle in the graph.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | We can build one backwards, by always finding a vertex which has no succeeding vertices, removing it from the graph and adding it to the front of our topologically sorted list.<br><br>This is not possible if there is a directed cycle in the graph. |
Note 5: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
By5dw(#>1%
Before
Front
Euclidian Division of polynomials in a field:
Back
Euclidian Division of polynomials in a field:
Theorem 5.25: Let \(F\) be a field. For any \(a(x)\) and \(b(x) \neq 0\) in \(F[x]\), there exists a unique \(q(x)\) (quotient) and unique \(r(x)\) (remainder) such that: \[ a(x) = b(x) \cdot q(x) + r(x) \quad \text{and} \quad \deg(r(x)) < \deg(b(x)) \]
This is analogous to integer division with remainder.
After
Front
How is Euclidian division of polynomials in a field defined?
Back
How is Euclidian division of polynomials in a field defined?
Theorem 5.25: Let \(F\) be a field. For any \(a(x)\) and \(b(x) \neq 0\) in \(F[x]\), there exists a unique \(q(x)\) (quotient) and unique \(r(x)\) (remainder) such that: \[ a(x) = b(x) \cdot q(x) + r(x) \quad \text{and} \quad \deg(r(x)) < \deg(b(x)) \]
This is analogous to integer division with remainder.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | <p>Euclidian |
<p>How is Euclidian division of polynomials in a field defined?</p> |
Note 6: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Cw4Jx2Tn6L
Before
Front
{{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\) \( \top\) and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}}\(\equiv\)\(F\) (tautology rules).
Back
{{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\) \( \top\) and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}}\(\equiv\)\(F\) (tautology rules).
After
Front
{{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\) \( \top\) and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}} \(\equiv\) \(F\).
Back
{{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\) \( \top\) and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}} \(\equiv\) \(F\).
(tautology rules)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | {{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\){{c2:: \( \top\)}} and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}}\(\equiv\){{c2::\(F\)}} |
{{c1::\(F \lor \top\) :: \(F \lor \text{or } \land \dots\)}} \(\equiv\){{c2:: \( \top\)}} and {{c1::\(F \land \top\)::\(F \lor \text{or } \land \dots\)}} \(\equiv\) {{c2::\(F\)}}. |
| Extra | (tautology rules) |
Note 7: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Tn2Bx6Km4H
Before
Front
\(F \land F\) \(\equiv\) \( F\) and \(F \lor F\) \(\equiv\) \( F\) (idempotence).
Back
\(F \land F\) \(\equiv\) \( F\) and \(F \lor F\) \(\equiv\) \( F\) (idempotence).
After
Front
\(F \land F\) \(\equiv\) \( F\) and \(F \lor F\) \(\equiv\) \( F\).
Back
\(F \land F\) \(\equiv\) \( F\) and \(F \lor F\) \(\equiv\) \( F\).
(idempotence)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | {{c1::\(F \land F\) :: <i>idempotence</i>}} \(\equiv\) {{c2:: \( F\)}} and {{c1::\(F \lor F\) :: <i>idempotence</i>}} \(\equiv\) {{c2:: \( F\)}} |
{{c1::\(F \land F\) :: <i>idempotence</i>}} \(\equiv\) {{c2:: \( F\)}} and {{c1::\(F \lor F\) :: <i>idempotence</i>}} \(\equiv\) {{c2:: \( F\)}}. |
| Extra | (idempotence) |
Note 8: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
q|}rXYFly~
Before
Front
Euler's totient function \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}}
Back
Euler's totient function \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}}
After
Front
Euler's totient function \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}}
Back
Euler's totient function \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}}
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | {{c1::Euler's totient function}} \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}} | {{c1::Euler's totient function::Name?}} \(\varphi: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+\) is defined as {{c2::the cardinality of \(\mathbb{Z}_m^*\): \[\varphi(m) = |\mathbb{Z}_m^*|\]}} |
Note 9: ETH::EProg
Deck: ETH::EProg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
bxDOHVL#p]
Before
Front
A compile error can result from an instanceof check if:
- Primitive types cannot be used with instanceof
- Cannot check for generics, type erasure prevents this.
t instanceof List<String>will not compile as it cannot check the parameterised type - Comparing siblings:
Animal -> DogandAnimal -> Cat.
Check foranimal instanceof Dog/Catallowed, butdog = new Dog(); dog instanceof Catthrows compile error. - Interface checks for
finalclasses (that don't implement that interface).
A final class cannot implement an interface in a subclass, thus error
Animal a = getanimal()could get aDogwhich
mightimplement Listthusa instanceof Listis not a compile error.
Back
A compile error can result from an instanceof check if:
- Primitive types cannot be used with instanceof
- Cannot check for generics, type erasure prevents this.
t instanceof List<String>will not compile as it cannot check the parameterised type - Comparing siblings:
Animal -> DogandAnimal -> Cat.
Check foranimal instanceof Dog/Catallowed, butdog = new Dog(); dog instanceof Catthrows compile error. - Interface checks for
finalclasses (that don't implement that interface).
A final class cannot implement an interface in a subclass, thus error
Animal a = getanimal()could get aDogwhich
mightimplement Listthusa instanceof Listis not a compile error.
After
Front
The cases where instanceof causes a compile error:
- Primitives - instanceof only works with reference types
- Generics - type erasure means List<String> becomes just List at runtime, so the check is impossible
t instanceof List<String> - Unrelated types:
Animal -> DogandAnimal -> Cat.
Check foranimal instanceof Dog/Catallowed, butdog = new Dog(); dog instanceof Catthrows compile error. - Final class - if a class is final and doesn't implement an interface, no subclass could ever implement it, so the check is provably always false.
Back
The cases where instanceof causes a compile error:
- Primitives - instanceof only works with reference types
- Generics - type erasure means List<String> becomes just List at runtime, so the check is impossible
t instanceof List<String> - Unrelated types:
Animal -> DogandAnimal -> Cat.
Check foranimal instanceof Dog/Catallowed, butdog = new Dog(); dog instanceof Catthrows compile error. - Final class - if a class is final and doesn't implement an interface, no subclass could ever implement it, so the check is provably always false.
However:
Animal a = getanimal() could get a Dog which might implement List thus a instanceof List is not a compile error.Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The cases where instanceof causes a compile error:<br><ol><li>{{c1::<b>Primitives - instanceof only works with reference types</b>}}</li><li>{{c2::Generics - type erasure means List<String> becomes just List at runtime, so the check is impossible<br><code> t instanceof List<String></code>}} </li><li>{{c3::Unrelated types:<br><div><code> Animal -> Dog</code> and <code>Animal -> Cat</code>. <br> Check for <code>animal instanceof Dog/Cat</code> allowed, but <code>dog = new Dog(); dog instanceof Cat</code> throws compile error.</div>}}</li><li><div>{{c4::Final class - if a class is final and doesn't implement an interface, no subclass could ever implement it, so the check is provably always false.}}</div></li></ol> | |
| Extra | However:<br><code>Animal a = getanimal()</code> could get a <code>Dog</code> which might <code>implement List</code> thus <code>a instanceof List</code> is not a compile error. |
Note 10: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
F@!OqZ7#Kb
Before
Front
For Least Squares, \(A\) needs to have linearly independent columns which they are if \(t_i = t_j\) for all \(i \not = j\) .
This is guaranteed if all datapoints are unique in time.
This is guaranteed if all datapoints are unique in time.
Back
For Least Squares, \(A\) needs to have linearly independent columns which they are if \(t_i = t_j\) for all \(i \not = j\) .
This is guaranteed if all datapoints are unique in time.
This is guaranteed if all datapoints are unique in time.
Otherwise the projection is not defined, i.e. there's no unique solution to the normal equations.
After
Front
For Least Squares, \(A\) needs to have linearly independent columns which they are if \(t_i = t_j\) for all \(i \not = j\) .
This is guaranteed if all datapoints are unique in time.
This is guaranteed if all datapoints are unique in time.
Back
For Least Squares, \(A\) needs to have linearly independent columns which they are if \(t_i = t_j\) for all \(i \not = j\) .
This is guaranteed if all datapoints are unique in time.
This is guaranteed if all datapoints are unique in time.
Otherwise the projection is not defined, i.e. there's no unique solution to the normal equations.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | For Least Squares, \(A\) needs to have {{c1:: linearly independent columns :: |
For Least Squares, \(A\) needs to have {{c1:: linearly independent columns ::what property and also why? }} which they are if {{c1:: \(t_i = t_j\) for all \(i \not = j\) }}.<br><br>This is guaranteed if all {{c2:: datapoints are unique in time}}. |
Note 11: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
KvqIdKEm_e
Before
Front
What happens if \(A\) itself is invertible for the projection matrix?
Back
What happens if \(A\) itself is invertible for the projection matrix?
It may look like we can simplify the expression for the projection matrix \(P\). This is not the case as \((A\top A)^{-1} = A^{-1} (A^\top)^{-1}\) is only the case if \(A\) itself is invertible.
But if \(A\) is invertible, it spans \(\mathbb{R}^m\) anyways and any projection is simply the point itself.
This is beautifully reflected in the fact that if we simplify \(P = A A^{-1} (A^\top)^{-1} A^\top\) then we simply get \(P = I\).
But if \(A\) is invertible, it spans \(\mathbb{R}^m\) anyways and any projection is simply the point itself.
This is beautifully reflected in the fact that if we simplify \(P = A A^{-1} (A^\top)^{-1} A^\top\) then we simply get \(P = I\).
After
Front
What happens if \(A\) itself is invertible for the projection matrix?
Back
What happens if \(A\) itself is invertible for the projection matrix?
Since \(A\) is invertible, it spans \(\mathbb{R}^m\) and any projection is simply the point itself.
This is beautifully reflected in the fact that if we simplify \(P = A A^{-1} (A^\top)^{-1} A^\top\) then we simply get \(P = I\).
In general it may look like we can simplify the expression for the projection matrix \(P\), this is however not the case, UNLESS \(A\) is invertible:
\((A^\top A)^{-1} = A^{-1} (A^\top)^{-1}\)
This is beautifully reflected in the fact that if we simplify \(P = A A^{-1} (A^\top)^{-1} A^\top\) then we simply get \(P = I\).
In general it may look like we can simplify the expression for the projection matrix \(P\), this is however not the case, UNLESS \(A\) is invertible:
\((A^\top A)^{-1} = A^{-1} (A^\top)^{-1}\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | Since \(A\) is <b>invertible</b>, it spans \(\mathbb{R}^m\) and any projection is simply the point itself.<br><br>This is <i>beautifully reflected</i> in the fact that if we simplify \(P = A A^{-1} (A^\top)^{-1} A^\top\) then we simply get \(P = I\).<br><br>In general it may look like we can simplify the expression for the projection matrix \(P\), this is however not the case, UNLESS \(A\) is invertible:<br><br>\((A^\top A)^{-1} = A^{-1} (A^\top)^{-1}\) |
Note 12: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
M~F%.[]]Xl
Before
Front
The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well defined. It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations {{c1:: \(A^\top A \hat{x} = A^\top b\) }}
Back
The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well defined. It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations {{c1:: \(A^\top A \hat{x} = A^\top b\) }}
After
Front
The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well-defined.
It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations{{c1:: \(A^\top A \hat{x} = A^\top b\) }}.
It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations{{c1:: \(A^\top A \hat{x} = A^\top b\) }}.
Back
The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well-defined.
It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations{{c1:: \(A^\top A \hat{x} = A^\top b\) }}.
It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the normal equations{{c1:: \(A^\top A \hat{x} = A^\top b\) }}.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well |
The projection of a vector \(b \in \mathbb{R}^m\) to the subspace \(S = C(A)\) is well-defined. <br><br>It can be written as \(proj_S(b) = A\hat{x}\) where \(\hat{x}\) satisfies the <b>normal equations</b>{{c1:: \(A^\top A \hat{x} = A^\top b\) }}. |
Note 13: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
dET3O3a8?c
Before
Front
A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).
When \(A\) has independent columns the unique minimiser of \(\hat{x}\) is given by \[ \hat{x} = {{c2::(A^\top A)^{-1} A^\top b }}\]
Back
A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).
When \(A\) has independent columns the unique minimiser of \(\hat{x}\) is given by \[ \hat{x} = {{c2::(A^\top A)^{-1} A^\top b }}\]
After
Front
A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).
When \(A\) has independent columns the unique minimiser of \(\hat{x}\) is given by: \[ \hat{x} = {{c2::(A^\top A)^{-1} A^\top b }}\]
Back
A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).
When \(A\) has independent columns the unique minimiser of \(\hat{x}\) is given by: \[ \hat{x} = {{c2::(A^\top A)^{-1} A^\top b }}\]
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <div>A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).</div><div>When \(A\) has {{c1::<b>independent columns</b>}} the {{c1::<b>unique</b>}} minimiser of \(\hat{x}\) is given by |
<div>A minimiser of \(\min_{\hat{x} \in \mathbb{R}^n} || A\hat{x} - b||^2\) is also a solution of \(A^\top A \hat{x} = A^\top b\).</div><div><br></div><div>When \(A\) has {{c1::<b>independent columns</b>}} the {{c1::<b>unique</b>}} minimiser of \(\hat{x}\) is given by: \[ \hat{x} = {{c2::(A^\top A)^{-1} A^\top b }}\]</div> |
Note 14: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
fTGz~gZIJt
Before
Front
If \(A^T A\) is invertible, we have a unique solution \(\hat{x}\) that satisfies the equation: \[ p = A\hat{x} = {{c1:: A (A^\top A)^{-1} A^\top b }}\]
Back
If \(A^T A\) is invertible, we have a unique solution \(\hat{x}\) that satisfies the equation: \[ p = A\hat{x} = {{c1:: A (A^\top A)^{-1} A^\top b }}\]
From \(A^\top A \mathbf{\hat{x}} = A^\top \mathbf{b}\) we can construct a formula for \(\mathbf{p}\): \((A^\top A)^{-1}(A^\top A) \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{b}\) (\(A^\top A\) invertible if the columns of \(A\) are independent), which gives us \(A \mathbf{\hat{x}} = A (A^\top A)^{-1} A^\top \mathbf{b} = \mathbf{p}\).
After
Front
If \(A^T A\) is invertible, we have a unique solution \(\hat{x}\) that satisfies the equation: \[ p = A\hat{x} = {{c1:: A (A^\top A)^{-1} A^\top b }}\]
Back
If \(A^T A\) is invertible, we have a unique solution \(\hat{x}\) that satisfies the equation: \[ p = A\hat{x} = {{c1:: A (A^\top A)^{-1} A^\top b }}\]
From \(A^\top A \mathbf{\hat{x}} = A^\top \mathbf{b}\) we can construct a formula for \(\mathbf{p}\):
\((A^\top A)^{-1}(A^\top A) \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{b}\)
(\(A^\top A\) invertible if the columns of \(A\) are independent), which gives us:
\(A \mathbf{\hat{x}} = A (A^\top A)^{-1} A^\top \mathbf{b} = \mathbf{p}\).
\((A^\top A)^{-1}(A^\top A) \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{b}\)
(\(A^\top A\) invertible if the columns of \(A\) are independent), which gives us:
\(A \mathbf{\hat{x}} = A (A^\top A)^{-1} A^\top \mathbf{b} = \mathbf{p}\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Extra | From \(A^\top A \mathbf{\hat{x}} = A^\top \mathbf{b}\) we can construct a formula for \(\mathbf{p}\): \((A^\top A)^{-1}(A^\top A) \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{b}\) (\(A^\top A\) invertible if the columns of \(A\) are independent), which gives us |
From \(A^\top A \mathbf{\hat{x}} = A^\top \mathbf{b}\) we can construct a formula for \(\mathbf{p}\): <br><br> \((A^\top A)^{-1}(A^\top A) \mathbf{\hat{x}} = (A^\top A)^{-1}A^\top \mathbf{b}\) <br><br>(\(A^\top A\) invertible if the columns of \(A\) are independent), which gives us:<br><br> \(A \mathbf{\hat{x}} = A (A^\top A)^{-1} A^\top \mathbf{b} = \mathbf{p}\). |
Note 15: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
f}{64fa3|!
Before
Front
A projection matrix is always symmetric (note that this needs to be reproven in the exam, proof included)
Back
A projection matrix is always symmetric (note that this needs to be reproven in the exam, proof included)
\(P^\top = (A(A^\top A)^{-1} A^\top)^\top =\) \((A^\top)^\top {(A^\top A)^{-1}}^\top A^\top = A(A^\top A)^{-1} A^\top = P\)
We use the fact that for invertible matrices \({M^{-1}}^\top = {M^\top}^{-1}\).
We use the fact that for invertible matrices \({M^{-1}}^\top = {M^\top}^{-1}\).
After
Front
A projection matrix is always symmetric (note that this needs to be reproven in the exam, proof included)
Back
A projection matrix is always symmetric (note that this needs to be reproven in the exam, proof included)
\(P^\top = (A(A^\top A)^{-1} A^\top)^\top =\) \((A^\top)^\top {(A^\top A)^{-1}}^\top A^\top = A(A^\top A)^{-1} A^\top = P\)
We use the fact that for invertible matrices \({M^{-1}}^\top = {M^\top}^{-1}\).
We use the fact that for invertible matrices \({M^{-1}}^\top = {M^\top}^{-1}\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | A projection matrix is always {{c1:: symmetric :: |
A projection matrix is always {{c1:: symmetric ::property?}} (<i>note that this needs to be reproven in the exam, proof included)</i> |
Note 16: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
n6JsTlECEy
Before
Front
Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then
\(\dim(V + W) = k + l \leq n\).
Back
Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then
\(\dim(V + W) = k + l \leq n\).
After
Front
Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then:
\(\dim(V + W) = k + l \leq n\).
Back
Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then:
\(\dim(V + W) = k + l \leq n\).
\(\dim(V + W) = \dim(V)+\dim(W)- \dim(V∩W) \)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <div>Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then</div><div> |
<div>Let \(V\) and \(W\) be orthogonal subspaces. If \(\dim(V) = k\) and \(\dim(W) = l\), then:</div><div><br></div><div></div><div></div><div></div><div>\(\dim(V + W) = {{c1::k + l}} \leq {{c1::n}}\).<br></div> |
| Extra | \(\dim(V + W) = \dim(V)+\dim(W)- \dim(V∩W) \) |
Note 17: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
nECE)EKh&n
Before
Front
When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking \(Ax\) to be the projection of \(b\) onto \(C(A)\).
Back
When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking \(Ax\) to be the projection of \(b\) onto \(C(A)\).
Least Squares is basically projection without multiplying by \(A\)at the end.
It's also basically the Pseudoinverse.
It's also basically the Pseudoinverse.
After
Front
When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking \(Ax\) to be the projection of \(b\) onto \(C(A)\).
Back
When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking \(Ax\) to be the projection of \(b\) onto \(C(A)\).
Least Squares is basically projection without multiplying by \(A\) at the end.
It's also basically the Pseudoinverse.
It's also basically the Pseudoinverse.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking {{c1:: |
When solving Least Squares (asking for a minimiser of \(||Ax - b||^2\)) we are asking {{c1::\(Ax\) to be the projection of \(b\) onto \(C(A)\)}}. |
| Extra | Least Squares is basically projection without multiplying by \(A\)at the end.<br>It's also basically the Pseudoinverse. | Least Squares is basically projection without multiplying by \(A\) at the end.<br><br>It's also basically the Pseudoinverse. |
Note 18: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
smJ/avn#*y
Before
Front
\(A^\top A\) is invertible if and only if \(A\) has linearly independent columns.
Back
\(A^\top A\) is invertible if and only if \(A\) has linearly independent columns.
After
Front
\(A^\top A\) is invertible if and only if \(A\) has linearly independent columns.
Back
\(A^\top A\) is invertible if and only if \(A\) has linearly independent columns.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | \(A^\top A\) is invertible |
\(A^\top A\) is invertible <i>if and only if</i> {{c1::\(A\) has linearly independent columns}}. |
Note 19: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
tX5`w6cN=$
Before
Front
Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\). The projection of \(b \in \mathbb{R}^m\) on \(S = \{\lambda a \ | \ \lambda \in \mathbb{R} \} = C(a)\) is given by \[ \text{proj}_S(b) = {{c1:: \frac{aa^\top}{a^\top a}b }}\]
This minimiser is unique.
Back
Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\). The projection of \(b \in \mathbb{R}^m\) on \(S = \{\lambda a \ | \ \lambda \in \mathbb{R} \} = C(a)\) is given by \[ \text{proj}_S(b) = {{c1:: \frac{aa^\top}{a^\top a}b }}\]
This minimiser is unique.
After
Front
Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\).
The projection of \(b \in \mathbb{R}^m\) on \(S = \{\lambda a \ | \ \lambda \in \mathbb{R} \} = C(a)\) is given by: \[ \text{proj}_S(b) = {{c1:: \frac{aa^\top}{a^\top a}b }}\]
This minimiser is unique.
Back
Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\).
The projection of \(b \in \mathbb{R}^m\) on \(S = \{\lambda a \ | \ \lambda \in \mathbb{R} \} = C(a)\) is given by: \[ \text{proj}_S(b) = {{c1:: \frac{aa^\top}{a^\top a}b }}\]
This minimiser is unique.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <div>Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\). |
<div>Let \(a \in \mathbb{R}^m \ \backslash \ \{0\}\). </div><div><br></div><div>The projection of \(b \in \mathbb{R}^m\) on \(S = \{\lambda a \ | \ \lambda \in \mathbb{R} \} = C(a)\) is given by: \[ \text{proj}_S(b) = {{c1:: \frac{aa^\top}{a^\top a}b }}\]</div><div>This minimiser is unique.</div> |