Modelling

Question 1

What is an optimisation problem?

Answer 1

An optimization problem is of the form
minimize f(x)
subject to x ∈ Ω
where f : R^n → R is a real-valued objective function and Ω ⊆ R^n is a set of constraints. If Ω = R^n, then the problem is an unconstrained optimization problem.

Question 2

What is the feasible set?

Answer 2

The set F = {x ∈ Rⁿ : f1(x) ≤ 0, . . . , fm(x) ≤ 0, g1(x) = 0, . . . , gp(x) = 0} is called the feasible set.

ie. the set of values x that satisfy the inequality and equality constraints.

Question 3

What are global and local minimizers?

Answer 3

A vector x∗ satisfying the constraints is called a solution or a global minimizer of the optimisation problem, if f(x*) ≤ f(x) for all other x that satisfy the constraints.
Besides global minimizers, there are also other types of minimizers. A point x∗ ∈ Ω is a local minimizer, if there is an open neighbourhood U of x∗ such that f(x∗) ≤ f(x) for all x ∈ U ∩ Ω. A local minimizer is called strict, if f(x∗) < f(x) for all x ∈ U ∩ Ω, and isolated if it is the only local minimizer in a small enough
neighbourhood.

Question 4

What is the Inner Product?

Answer 4

Essentially dot product.
⟨x, y⟩ = x · y = x⊺y = ∑_i=1ⁿ xiyi.

Question 5

What are the 3 important norms?

Answer 5

Three important examples of norms are the following:
1. The 1-norm: ∥x∥₁ = ∑_i=1ⁿ |xi|;
2. The 2-norm: ∥x∥₂ = sqrt[∑_i=1ⁿ xi²]
3. The ∞-norm: ∥x∥_∞ = max_1≤i≤n |xi|.

Question 6

When is a matrix positive definite and semidefinite?

Answer 6

A symmetric matrix A is called positive semidefinite, written A ⪰ 0, if for all non-zero x ∈ R^n, x⊺Ax ≥ 0, and positive definite, written A ≻ 0, if x⊺Ax > 0 for all x ̸= 0. Equivalently, a symmetric matrix is positive semidefinite if all its eigenvalues are non-negative, and positive definite if they are all positive.

Question 7

What is a Convex Set?

Answer 7

A set C ⊆ R^n is a convex set, if for all x, y ∈ C and λ ∈ [0, 1], λx + (1 − λ)y ∈ C. A compact (closed and bounded) convex set is called a convex body.

Question 8

What do we know about the intersection, sum and scalar product of convex sets?

Answer 8

Let C, D ∈ C(R^n) be convex sets. Then the following are also convex.
* C ∩ D;
* C + D = {x + y | x ∈ C, y ∈ D};
* AC = {Ax | x ∈ C}, where A ∈ R^m×n
.

Question 9

What is the Convex hull?

Answer 9

The convex hull conv S of a set S is the intersection of all convex sets containing S. Clearly, if S is convex, then S = conv S.

We have
conv S = {x ∈ R^n | x = ∑_i=1^k λixk, xi ∈ S, ∑_i=1^k λi = 1, λi ≥ 0}.

Question 10

What can we tell about the distance between points in and not in a convex set?

Answer 10

Let C be a non-empty convex set and x ̸∈ C. Then there exists a point y ∈ C that minimizes the distance ∥x − y∥. Moreover, for all z ∈ C we have
⟨z − y, x − y⟩ ≤ 0.
In words, the vectors z − y and x − y form an obtuse angle.

Question 11

How can we find a hyperplane between a point and convex set?

Answer 11

In what follows write intS for the interior of a set S.

Let C be a closed convex set and x ̸∈ C. Then there exists a hyperplane H such that
C ⊂ intH− and x ∈ intH+.

Question 12

What is a Convex function?

Answer 12

Let S ⊆ R^n. A function f : S → R is called convex if S is convex and for all v, w ∈ S
and λ ∈ [0, 1], f(λv + (1 − λ)w) ≤ λf(v) + (1 − λ)f(w). The function f is called strictly convex if f(λv + (1 − λ)w) < λf(v) + (1 − λ)f(w). A function f is called concave, if −f is convex.

Question 13

What is any local minimizer also in a convex function?

Answer 13

Let f : R^d → R be a convex function. Then any local minimizer of f is a global minimizer.

Proof.
Let v∗ be a local minimizer and assume that it is not a global minimizer. Then there exists a vector w ∈ R^d such that f(w) < f(v∗). Since f is convex, for any λ ∈ [0, 1] and v = λw + (1 − λ)v∗ we have
f(v) ≤ λf(w) + (1 − λ)f(v∗) < λf(v∗) + (1 − λ)f(v∗) = f(v∗).
This holds for all v on the line segment connecting w and v∗. Since every open neighbourhood U of v∗ contains a bit of this line segment, this means that every open neighbourhood U of v∗ contains an v ̸= v∗ such that f(v) ≤ f(v∗), in contradiction to the assumption that v∗ is a local minimizer. It follows that v∗ has to be a global minimizer.

Question 14

How can we characterise convex functions using differentiability?

Answer 14

1. Let f ∈ C1(R^d). Then f is convex if and only if for all v, w ∈ R^d,
   f(w) ≥ f(v) + ∇f(v)⊺(w − v).
2. Let f ∈ C2(R^n). Then f is convex if and only if ∇2f(v) is positive semidefinite for all v. If ∇2f(v) is positive definite for all v, then f is strictly convex.

Question 15

What are iterative algorithms?

Answer 15

Most modern optimization methods are iterative: they generate a sequence of points x0, x1, . . . in R^d in the hope that this sequences converges to a local or global minimizer x∗ of a function f(x). A typical rule for generating such a sequence is to start with a vector x0, chosen by an educated guess, and then for k ≥ 0, move from step k to k + 1 by
xk+1 = xk + αkpk, in a way that ensures that f(xk+1) ≤ f(xk). The parameter αk is called the step length (or learning rate in machine learning), while pk is the search direction.

Question 16

What is Gradient Descent?

Answer 16

In the method of gradient descent, the search direction is chosen as
pk = −∇f(xk).
To see why this makes sense, let p be a direction and consider the Taylor expansion
f(xk + αp) = f(xk) + αp⊺∇f(xk) + O(α^2).
Considering this as a function of α, the rate of change in direction p at xk is the derivative of this function at α = 0,
df(xk + αp)/dα|α=0 = ⟨p, ∇f(xk)⟩,
also known as the directional derivative of f at xk in the direction p. This formula indicates that the rate of change is negative, and we have a descent direction, if ⟨p, ∇f(xk)⟩ < 0.

Question 17

What are the different types of convergence?

Answer 17

Assume that a sequence of vectors {xk}, k ≥ 0, converges to x∗. Then the sequence
{xk}, k ≥ 0, is said to converge:
(a) linearly (or Q-linear, Q for quotient), if there exist an r ∈ (0, 1) such that for sufficiently large k,
∥xk+1 − x∗∥ ≤ r∥xk − x∗∥.
(b) superlinearly, if
lim_k→∞∥xk+1 − x∗∥/∥xk − x∗∥ = 0,
(c) with order p, with p > 1, if there exists a constant M > 0, such that for sufficiently large k,
∥xk+1 − x∗∥ ≤ M∥xk − x∗∥^p.
The case p = 2 is called quadratic convergence.

Question 18

What is Newton’s Method?

Answer 18

Let f ∈ C^2(R^n) and let’s look again at the unconstrained problem
minimize f(x).
Newton’s method starts with a guess x0 and then proceeds to compute a sequence of points {xk}k≥0 in R^n by the rule
xk+1 = xk − ∇^2f(xk)^−1∇f(xk), k ≥ 0.
The algorithm stops when ∥xk+1 − xk∥ < ε for some predefined tolerance ε > 0. In the context of the general scheme xk+1 = xk + αkpk, the step length is αk = 1, and the search direction is the inverse of the Hessian multiplied with the negative gradient.

Question 19

What neighbourhood can we find around a point where ∇^2 is positive definite at that point?

Answer 19

Let x∗ ∈ R^n be such that ∇2f(x∗) is positive definite. Then there exists an open neighbourhood U of x∗ such that for all x ∈ U, ∇2f(x) is positive definite.

Question 20

When is a function Lipschitz continuous?

Answer 20

A function f : R^n → R^m is Lipschitz continuous on a domain Ω ⊆ R^n with respect to a pair of norms on R^n and R^m if there is a constant L > 0 such that for all x, y ∈ Ω,
∥f(x) − f(y)∥ ≤ L∥x − y∥.
The constant L is called the Lipschitz constant of the map.

In particular, the Hessian of a function f ∈ C^2(R^n), considered as a map from R^n
to R^n×n, is Lipschitz continuous with respect to a norm on R^n and the corresponding operator norm on R^n×n, if for any x, y we have
∥∇^2f(x) − ∇^2f(y)∥ ≤ L∥x − y∥.

Question 21

When will Newton’s method have quadratic convergence?

Answer 21

Let f ∈ C^2(R^n) with Lipschitz continuous Hessian, and let x∗ ∈ R^n be a local minimizer with ∇f(x∗) = 0 and ∇2f(x∗) > 0. Then for x0 sufficiently close to x∗, Newton’s method has quadratic convergence.

Question 22

What is a Linear Programming problem?

Answer 22

Linear programming is about problems of the form
maximize ⟨c, x⟩
subject to Ax ≤ b,
where A ∈ R^m×n, x ∈ R^n, c ∈ R^n, and b ∈ R^m, and the inequality sign means inequality in each row.
The feasible set is the set of all possible candidates,
F = {x ∈ R^n | Ax ≤ b}.

Question 23

How can we check a linear programming problem has a solution?

Answer 23

A first important task is to find out if there exist any feasible solutions at all. That is, we would like to know if the system of linear inequalities Ax ≤ b has a solution. If F is not empty, we can certify that by producing a vector from F. To verify that the feasible set is empty is more tricky: we are asked to show that no vector lives in F. What we can try to do, however, is to show that the assumption of a solution to Ax ≤ b would lead to a contradiction.
Denote by a⊺i the rows of A, so that the entries of Ax are given by a⊺i x for 1 ≤ i ≤ m. Assuming x ∈ F, then given a vector 0 ̸= λ = (λ1, . . . , λm)⊺ with λi ≥ 0, the linear combination satisfies
⟨λ, Ax⟩ =
∑_i=1^m λia⊺ix ≤
∑_i=1^m λibi = ⟨λ, b⟩.
If we can find parameters λ such that the left-hand side is identically 0 and the right-hand side is strictly negative, then we have found a contradiction and can conclude that no x satisfies Ax ≤ b. A
condition that ensures this is
∑_i=1^m λiai = 0, ⟨λ, b⟩ < 0.
In matrix form,
∃λ ≥ 0, A⊺λ = 0, ⟨λ, b⟩ < 0.

Question 24

What is a Polyhedron?

Answer 24

A polyhedron (plural: polyhedra) is a set defined as the solution of linear equalities and inequalities,
P = {x ∈ R^n | Ax ≤ b},
where A ∈ R^m×n, b ∈ R^m.

Question 25

What is a Polytope?

Answer 25

A polytope is the convex hull of finitely many points,
P = conv({x1, . . . , xk}) = {∑_i=1^k λixi, λi ≥ 0, ∑_i λi = 1}.

Question 26

What is bounded polyhedron?

Answer 26

A bounded polyhedron P is the convex hull of its vertices.

Question 27

How do polytopes and polyhedrons relate?

Answer 27

A polytope is a bounded polyhedron.

Question 28

How can hyperplanes separate cones and the plane?

Answer 28

Let C ̸= R^n be a closed convex cone and z ̸∈ C. Then there exists a linear hyperplane such that C ⊆ H− and z ∈ intH+.

Question 29

What is Farkas’ Lemma?

Answer 29

Given a matrix A ∈ R^m×n and b ∈ R^m, there exists a vector x such that Ax = b, x ≥ 0 if and only if there is not y ∈ R^m such that
A⊺y ≥ 0, ⟨y, b⟩ < 0.

Question 30

What are the consequences of Farkas’ Lemma?

Answer 30

Given a matrix A ∈ R^m×n and b ∈ R^m, there exists a vector x ̸= 0 such that
Ax ≤ b
if and only there is no y such that
y ≥ 0, A⊺y = 0, ⟨y, b⟩ < 0.

Let A ∈ R^m×n and b ∈ R^m. Then for δ > 0 and every vector x ∈ R^n with Ax ≤ b,
⟨c, x⟩ ≤ δ holds if and only if there exists y ∈ R^m such that
y ≥ 0, A⊺y = c, ⟨y, b⟩ ≤ δ.

Question 31

What is the Duality Theorem?

Answer 31

Let A ∈ R^m×n, b ∈ R^m and c ∈ R^n. Then the optimal value of
maximize⟨c, x⟩ subject to Ax ≤ b (P)
coincides with the optimal value of
minimize⟨b, y⟩ subject to A⊺y = c, y ≥ 0, (D)
provided both (P) and (D) have a finite solution.

Proof:
Let P = {x | Ax ∈ b} and D = {y ∈ R^m | A⊺y = c, y ≥ 0}. If x ∈ P and y ∈ Q, then
⟨c, x⟩ = ⟨A⊺y, x⟩ = ⟨y, Ax⟩ ≤ ⟨y, b⟩,
so that in particular
max,x∈P ⟨c, x⟩ ≤ min,y∈Q ⟨b, y⟩,
which shows one inequality. To show the other inequality, set δ = maxx∈P ⟨c, x⟩. By definition, if
Ax ≤ b, then ⟨c, x⟩ ≤ δ. By Corollary 9.4, there exists a vector y ∈ R^m such that
y ≥ 0, A⊺y = c, ⟨b, y⟩ ≤ δ.
In particular,
min,y∈Q ⟨b, y⟩ ≤ δ = max,x∈P ⟨c, x⟩.

Question 32

How can we find a minimiser to a constrained convex optimisation problem?

Answer 32

Let f ∈ C1(R^d) be a convex, differentiable function, and consider a convex optimization problem of the form (P). Then x∗ is a minimizer of the optimization problem minimize f(x) subject to x ∈ F
if and only if for all x ∈ F, ∇f(x∗)⊺(x − x∗) ≥ 0, (10.1)
where F is the feasible set of the problem.

Proof.
Suppose x∗ is such that (10.1) holds. Then, since f is a convex function, for all x ∈ F we have, f(x) ≥ f(x∗) + ⟨∇f(x∗),(x − x∗)⟩ ≥ f(x∗), which shows that x∗ is a minimizer in F. To show the opposite direction, assume that x∗ is a minimizer but that (10.1) does not hold. This means that there exists a x ∈ F such that ⟨∇f(x∗),(x − x∗)⟩ < 0.
Since both x∗ and x are in F and F is convex, any point v(λ) = (1 − λ)x∗ + λx with λ ∈ [0, 1] is also in F. At λ = 0 we have
df/dλ f(v(λ))|λ=0 = ⟨∇f(x∗),(x − x∗)⟩ < 0.
Since the derivative at λ = 0 is negative, the function f(v(λ)) is decreasing at λ = 0, and therefore, for small λ > 0, f(v(λ)) < f(v(0)) = f(x∗), in contradiction to the assumption that x∗is a minimizer.

Question 33

What is the Lagrangian of a convex problem?

Answer 33

We consider the following convex problem minimize_x f(x)
subject to f(x) ≤ 0
h(x) = 0,
Denote by D the domain of all the functions f, fi, hj , i.e.,
D = dom(f) ∩ dom(f1) ∩ · · · ∩ dom(fm) ∩ dom(h1) ∩ · · · ∩ dom(hp).
Assume that D is not empty and let p∗ be the optimal value of this problem.
The Lagrangian of the system is defined as
L(x,λ, µ) = f(x) + λ⊺f(x) + µ⊺h(x) = f(x) + ∑_i=1^m λifi(x) + ∑_i=1^p µihi(x).

The vectors λ and µ are called the dual variables or Lagrange multipliers of the system. The domain of L is D × R^m × R^p.

Question 34

What is the Lagrange Dual?

Answer 34

The Lagrange dual of the convex problem is the function
g(λ, µ) = infx∈D L(x,λ, µ).
If the Lagrangian L is unbounded from below, then the value is −∞.

Question 35

How does the Lagrange dual relate to the optimal value?

Answer 35

Let p∗ be the optimal value of the convex problem. Then for any µ ∈ R^p and λ ≥ 0 we have
g(λ, µ) ≤ p

Question 36

What is the Lagrange dual problem?

Answer 36

The Lagrange dual problem of the convex optimization problem is the problem
maximize g(λ, µ) subject to λ ≥ 0.
If d∗ is the optimal value of this, then d∗ ≤ p∗. In the special case of linear programming we actually have d∗ = p∗.

Question 37

What is Strong Duality?

Answer 37

When the primal and dual optimal solutions are equal, p* = d*.

Question 38

What is the Slater condition?

Answer 38

Assume that the interior of the domain D of (P) is non-empty, that the problem (P) is convex, and that there exists a point x ∈ D such that
fi(x) < 0, 1 ≤ i ≤ m, Ax = b, 1 ≤ j ≤ p.
Assume that A has maximal rank. Then d∗ = p∗.

Question 39

What are the KKT Conditions?

Answer 39

Let x∗ and (λ∗, µ∗) be primal and dual optimal solutions of (11.5) with zero duality gap. The the following conditions are satisfied:
f(x∗) ≤ 0 (note this f is the inequality conditions, not objective function)
h(x∗) = 0
λ∗ ≥ 0
λ∗ifi(x∗) = 0, 1 ≤ i ≤ m
∇xf(x∗) + ∑_i=1^m λ∗i ∇xfi(x∗) + ∑_j=1^p=1 µ∗j∇xhj (x∗) = 0.
Moreover, if the problem is convex and the Slater Conditions are satisfied, then any points satisfying the KKT conditions have zero duality gap.

Question 40

What is the Weierstrass Approximation Theorem?

Answer 40

Suppose that f is a real valued function, defined and continuous on a bounded closed interval [a, b] of the real line. Then given any ε > 0 there exists a polynomial p such that
∥f − p∥∞ ≤ ε.
The same result holds in the 2− norm if the weight function w is real valued, positive, continuous and integrable on (a, b).

Question 41

What is Best Approx in the ∞-Norm?

Answer 41

Consider a polynomial qn ∈ Pn of the form qn(x) = c0 + c1x + . . . + cnx^n and define the function
E : (c0, . . . cn) ∈ R^n+1 → E(c0, c1, . . . cn) as
E(c0, c1, . . . cn) = ∥f − qn∥∞
= max x∈[a,b] |f(x) − c0 − c1x − . . . cnx^n|

ie. need to find poly q such that f-q is minimised wrt the ∞-Norm.

Question 42

How does the Best Approx in the ∞-Norm exist?

Answer 42

Let f ∈ C[a, b]. Then there exists a polynomial pn ∈ Pn such that
∥f − p∥∞ = min q∈Pn ∥f − q∥∞.

Question 43

How can we find the best approx in the ∞-norm of degree 0?

Answer 43

Generally, if we drop the monotonicity assumption on f and assume that ξ and ζ are two points in [a, b] where f attains its minimum and maximum, then the minimax polynomial of degree 0 is given by p0(x) = 1/2 * (f(ξ) + f(ζ)), x ∈ [a, b].

Question 44

What is the Oscillation Theorem?

Answer 44

Let f ∈ C[a, b]. A polynomial pn ∈ Pn is a minimax polynomial for f on [a, b], if and only if, there exists a sequence of n + 2 points xi, i = 0, 1, . . . n + 1 such that 0 ≤ x0 < . . . < xn+1 ≤ b with
|f(xi) − pn(xi)| = ∥f − pn∥∞ i = 0, 1, . . . n + 1
and
f(xi) − pn(xi) = − (f(xi+1 − pn(xi+1)), i = 0, . . . n.
In other words, the theorem says that f − pn attains its maximum absolute value with alternating signs at the points xi. The points xi are often referred to as the critical points.

Question 45

How can we find the best approx in the ∞-norm of degree 1?

Answer 45

We will use the oscillation theorem to construct a minimax polynomial of order one for a function f ∈ C[a, b] with strictly monotonically increasing f′. We seek p1 ∈ P1 of the form
p1(x) = c0 + c1x.

The difference f − (c0 + c1x) attains its extrema either at the endpoints of [a, b] or at points where f′(x) − c1 is zero. Since f′ is strictly monotonically increasing it can only take the value c1 at a single point only, and therefore the endpoints a and b are critical points. Let d denote the third critical point inside the interval [a, b] and whose location remains to be determined. At x = d we have that
(f(x) − (c1x + c0))′|x=d= 0.

By the oscillator theorem with x0 = a, x1 = d and x2 = b we have that
f(a) − (c1a + c0) = A (15.1a)
f(d) − (c1d + c0) = −A (15.1b)
f(b) − (c1b + c0) = A (15.1c)
where A either takes the value A = L or A = −L with L = maxx∈[a,b]
|f(x) − p1(x)|. Since
f′(d) = c1 (15.2)
this gives us enough equations to compute d, c0, c1 and A.

Question 46

What are Chebyshev Polynomials?

Answer 46

The Chebyshev polynomials of degree n are defined as follows:
Tn(x) = cos(n cos−1 x) for n = 0, 1, 2, . . . and x ∈ [−1, 1].

Although it is not immediately clear, Tn are in fact polynomials. For example, the first three Chebyshev polynomials on [−1, 1] are:
T0(x) = 1
T1(x) = x
T2(x) = 2x^2 − 1

Question 47

What are the known statements the Chebyshev polynomials satisfy?

Answer 47

Consider the Chebyshev polynomials Tn as defined in (15.3). Then Tn satisfy
1. Tn+1(x) = 2xTn(x) − Tn−1(x), x ∈ [−1, 1] and n = 1, 2, 3 . . .
2. Tn is a polynomial of order n with leading coefficient 2^n−1x^n for n ≥ 1.
3. Tn is even on [−1, 1] if n is even, and odd if n is odd.
4. The real and distinct zeros of Tn are given by
xj = cos((2j − 1)π/2n), j = 1, . . . n.
5. |Tn(x)| ≤ 1 for all x ∈ [−1, 1]
6. Tn alternates between 1 and −1 at the points xk = cos( kπ/n ), k = 0, 1, . . . , n.

Question 48

What is the minimax approximation to the function x → x^(n+1)?

Answer 48

Let n ≥ 0 and consider the polynomial pn ∈ Pn given by
pn(x) = x^n+1 + (2^−n)Tn+1(x), x ∈ [−1, 1]
Then pn is the minimax approximation of degree n to the function x → x^n+1 on the interval [−1, 1].

Question 49

What polynomials are the best approximation to monomic polynomials?

Answer 49

Let n ≥ 0. Among all monomic polynomials of degree n + 1 the poynomials
2^−n * Tn+1 and −2^−n * Tn+1 have the smallest ∞-norm on the interval [−1, 1].

Question 50

What is the Approx. in the 2-Norm?

Answer 50

The best approximation problem in the 2 norm is given by
Given a function f ∈ L^2w(a, b), find a polynomial p ∈ Pn such that
∥f − pn∥2 = infq∈Pn ∥f − q∥2.

Question 51

What are orthogonal polynomials?

Answer 51

Let w be an integrable, positive and continuous weight function on (a, b). Consider a sequence of polynomials φj , j = 1, . . .. If
∫a,b w(x)φi(x)φj (x) dx = (0 for all i ̸= j, 1 if i = j,)
we call the sequence φi, i = 1, . . . a system of orthogonal polynomials.

Question 52

How does the best approx in the 2 norm exist and is it unique?

Answer 52

Let f ∈ L^2w(a, b), then there exists a unique polynomial pn ∈ Pn such that
∥f − pn∥2 = min q∈Pn ∥f − q∥2

Question 53

When is a polynomial the best approx in the 2 norm?

Answer 53

Let f ∈ L^2w(a, b). A polynomial pn ∈ Pn is the polynomial of best approximation in the 2 norm, if and only if
⟨f − pn, q⟩ = 0 for all q ∈ Pn
That is, the difference f − pn is orthogonal to every element in Pn.

Question 54

How can we use a sequence of orthogonal polynomials to get a best approx in the 2 norm?

Answer 54

First, constructing a sequence of orthogonal polynomials φj , j = 0, 1, . . . n on the interval (a, b) with respect to the weight function w. Then normalise the polynomials by setting
ψj = φj/∥φj∥, j = 0, 1, . . . n
to obtain orthonormal polynomials and evaluate the coefficients ψj , j = 0, 1, . . . n on (a, b). Next compute the coefficients
β∗j = ⟨f, ψj ⟩, j = 0, 1, . . . n to obtain
pn = β∗0ψ0(x) + . . . β∗nψn(x).

Question 55

What is a Trigonometric Polynomial?

Answer 55

A trigonometric polynomial of degree n is a function of the form
a0 + ∑_k=1ⁿ (ak cos kx + bk sin kx)
with coefficients a0, a1, . . . , an, b1, . . . bn in R.
If the sum represents an even function, then it can be written using only cosines.

Question 56

What is Weierstrass Second Theorem?

Answer 56

Let f ∈ C^2π . Then there exists a trigonometric polynomial pn ∈ Tn for every ε > 0, such that
∥f − pn∥∞ < ε.

Question 57

What is a Fourier Series?

Answer 57

m. The Fourier series of a 2π
periodic, bounded and integrable function is given by
F(x) = a0/2 + ∑_k=1^∞ (ak cos kx + bk sin kx)
where the coefficients are defined by
ak = 1/π ∫_-π^π f(x) cos kx dx and bk = 1/π ∫_-π^π f(x) sin kx dx

Question 58

How does the Fourier transform simplify for even and odd functions?

Answer 58

The Fourier transform simplifies considerably if f is an even or an odd function. In particular,
* if f is even and real-valued then (19.1) reduces to a cosine series, that is bk = 0 for all k = 1, 2, . . ..
* if f is odd and real-valued then (19.1) reduces to a sine series, that is ak = 0 for all k = 0, 1, . . ..

Question 59

What is the partial sum of a Fourier series?

Answer 59

Fn(x) = a0/2 + ∑_k=1ⁿ (ak cos kx + bk sin kx)

Question 60

What is the discrete Fourier Transform?

Answer 60

The discrete Fourier transform is the transformation of the vector f = (f0, . . . , fn) to ck and is therefore given by
ˆfk = ∑_j=0^n-1 wn^−kj fj, 0 ≤ k ≤ n − 1.
where wn = e^2πi/n .

Question 61

What are the properties of the DFT?

Answer 61

The DFT has the following properties
* Linear Shift: ˆf(k − j) = ˆf(k)e^−2πij/n
* Frequency Shift: f(\k)e^2πij/n = ˆf(k − j).

Question 62

What are the types of compression?

Answer 62

Compression can be classified as lossless or lossy. In lossless compression (such as zip or tar files), one regains the original data without loss after compression. This is not the case in lossy compression, where some information is lost/discarded. The reconstructed images are therefore of lower quality than the
original.