CompSci 520 HW-1: warm-up Spring 2021
1 Analysis
1.1 Filtering by projections
Consider the vector space V = Rn over the field R. Assume that V is equipped with a well defined
inner product
〈u, v〉 = uTWv (1)
1. [Y/N/M] The inner product is well defined if and only if W is symmetric positive definite
(s.p.d.)
2. [Y/N/M] For any fixed vector u 6= 0, the unary function 〈u, v〉 is a scalar-valued function
linear with v. Conversely, any scalar-valued function f(v) linear with v can be represented
as f(v) = 〈u, v〉 for some vector u.
Optional. Verify that any linear function f : Rn 7→ Rm, m ≥ 1, can be written as
f(v)T = (〈u1, v〉, 〈u2, v〉, · · · , 〈um, v〉) , specifically, f(v) = (UTW )v
for m vectors ui, i = 1, 2, · · · ,m, and U = [u1, u2, · · · , um].
3. Verify that the inner-product induced unary function
‖u‖W = (〈u, u〉)1/2 (2)
is a well-defined vector norm on V . Verify further that ‖u − v‖W is a well defined distance
function.
Describe also the mapping from V to the unit sphere with respect to the norm ‖ · ‖W .
4. Provided with two nonzero vectors x and a, x, a ∈ Rn. Describe the orthogonal decomposition
of x into tow components, one is along a, the other is orthogonal to a, with respect to the
inner product (1). Describe the least deviation of x from the a-axis.
Similarly, describe the deviation of a from the x-axis.
5. [Y/N/M] Assume W = I. Let A1 ∈ Rm×n. Let (σ1, u1, v1) be the leading tuple of singular
value and singular vectors. Let (σ2, u2, v2) be the leading tuple of singular value and singular
vectors of the matrix
A2 = A1 − σ1u1vT1 .
Then,
σ1 ≥ σ2, 〈u1, u2〉 = 0, 〈v1, v2〉 = 0.
Optional. Extend the above relationship to Ak, 2 < k ≤ rank(A).
1
CompSci 520 HW-1: warm-up Spring 2021
1.2 Data modeling or fitting: architecture & algorithms
Provided with a finite set of discrete points
(xi, yi), i = 0, 1, 2, · · · , n (3)
Consider a linear model architecture
f(x) =
∑
j=0:m
fjbj(m), m ≥ 0 (4)
where bj(x), 0 ≤ j ≤ m, are linearly independent functions over [mini{xi},maxi′{xi′}]. Let
B = [bj(xi)| 0 ≤ i ≤ n, 0 ≤ j ≤ m] (5)
1. [Y/N/M] Matrix B depends on the sample locations {xi}. It is not necessarily of full column
rank.
2. [Y/N/M] There exists an interpolant if and only if y ∈ colspan(B). There exists a unique
interpolant if and only if B is of full column rank.
3. [Y/N/M] The fitting problem may of may not have a solution.
4. Give the conditions for the solution to the fitting problem, when it exists, to be unique.
Describe the relationship among all solutions otherwise.
5. Consider the effect of specific model structures on model solution process.
(a) Verify that matrix B is lower triangular when the basis functions are the Newton poly-
nomials
b0(x) = 1, b1(x) = (x− x0), · · · , bj(x) =
∏
k=0:(j−1)
(x− xk), j ≤ m ≤ n. (6)
Describe the solution process for both the interpolation problem and the fitting problem.
(b) Verify that matrix B is diagonal when the basis functions are the Lagrange polynomials
bj(x) =
∏
k 6=j(x− xk)∏
k 6=j(xj − xk)
, j ≤ m = n. (7)
Describe the solution process for both the interpolation problem and the fitting problem.
Optional. Describe the structure of piecewise polynomial model subject to the feasibility condition
that a candidate interpolant or fitting function has continuous second derivative.
2
CompSci 520 HW-1: warm-up Spring 2021
2 Experiments
2.1 Experiment-1: compression & reconstruction via SVD
We are provided with reference codes for image compression via a truncated SVD, transmission
and reconstruction, post-evaluation, and visualization. See the sub-directory svd sequence.
Basic facts: The time complexity for the SVD of an m×n dense data array (such as an image) with
numerical computation is c× (nmr+ r3), where r ≤ rank(A) is the numerical rank with respect to
a threshold and c is a modest constant by some good SVD algorithms. The spatial complexity of
the output is r × (m+ n+ 1).
1. Find and state some conditions under which it is beneficial to partition the image into sub-
images, and make SVDs on each and every sub-image.
2. Extend the reference codes for image compression, reconstruction and post-evaluation on
partitioned sub-images. Visualize intermediate and final results whenever available.
Optional. Speed up the image restoration codes by the transport inpainting related function(s)
and script(s), under the sub-directory inpainting.
2.2 Experiment-2: higher-resolution reconstruction via interpolation
We are provided with a test function and a set of 64 × 64 samples of the test function. See the
script test image upsample under the sub-directory interpolation.
1. Make upsampling by 6 times over the first line of samples, via 1D interpolation, using at least
three different interpolation schemes, self-made or available on MATLAB.
Provide visualization of the upsampled curves and the residual curves (against the ground
truth).
2. Make upsampling over the entire set of the samples, 6× in each dimension, via 2D interpola-
tion, using at least three different interpolations schemes, available on MATLAB.
Provide visualization of the upsampled images and the residual images (against the ground
truth).
Optional. Present a novel 2D interpolation scheme with higher accuracy.
Optional. Present a better image reconstruction with combined use of SVD compression and
interpolation.
3
学霸联盟