xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

matlab代写-HW-1

时间：2021-03-03

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

学霸联盟

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

学霸联盟