• Submit your electronic copy (a single PDF and MATLAB code) to the dropbox in Waterloo
LEARN.
• Your MATLAB code has to be executable. That is, error free. Points will be deducted for code
with error(s).

## 1 Image completion (100 points)

You are given a “corrupted image” $X_{\text {corrupted }} \in \mathbb{R}^{n \times n}$. In the dataset, there are two images, the “cammerman” (a 128-by-128 matrix, as shown in Figure 1) and the “mario” (a 50-by-50 matrix, as shown in Figure 2). Your goal is to repair such image. That is, you want to get $X \in \mathbb{R}^{n \times n}$ that represent the repaired $X_{\text {corrupted }}$.

Figure 2 shows the corrupted mario image contains numbers from 0 to 254 , and 255 (white color) represents a broken pixel value.

Refer to the lecture on image inpainting, the mathematics of such “completion” is to solve the following optimization problem
$$\begin{array}{cl} \min & |\mathrm{Ex}|_{1} \ \text { s.t. } & \mathrm{Sx}=\hat{\mathrm{x}}_{\Omega} \ & \mathrm{x} \geq 0 \end{array}$$

where

• $\mathrm{X} \in \mathbb{R}^{n \times n}$ is the repaired image, which is a matrix
• $\mathrm{x} \in \mathbb{R}^{n^{2}}$ is the vectorized image. It is the vectorized version of $\mathrm{X}$. Here, we perform vectorization to turn the matrix $\mathbf{X}$ to a vector so that we can run LP code to find it.
• $|\mathrm{Ex}|_{1}$ is called the “Total Variation” (TV) of the vector $\mathbf{x}$, where $\mathbf{E}$ is a given matrix that compute the “variation” of the vector $\mathrm{x}$.
• $\mathrm{S} \in \mathbb{R}{+}^{|\Omega| \times n^{2}}$ is a sub-matrix of $\mathbf{I}{n^{2}}$ consists of rows labeled in the set $\Omega$, which label which pixel we have observed in the image
• $\hat{\mathbf{x}}{\Omega} \in \mathbb{R}{+}^{|\Omega|}$ is the clean part of the observed image, with $|\Omega|<n^{2}$ number of entries.
Given $\mathbf{E} \in \mathbb{R}^{2 n(n-1) \times n^{2}}, \mathbf{S} \in \mathbb{R}{+}^{|\Omega| \times n^{2}}$, and $\hat{\mathbf{x}}{\Omega} \in \mathbb{R}_{+}^{|\Omega|}$, write a program to solve Problem $*$. Plot the recovered image. There are 2 images in the data file, try with mario.m (the smaller one) first. See a7_main.m in the data file for details.

Given $\mathbf{E} \in \mathbb{R}^{2 n(n-1) \times n^{2}}, \mathbf{S} \in \mathbb{R}{+}^{|\Omega| \times n^{2}}$, and $\hat{\mathbf{x}}{\Omega} \in \mathbb{R}_{+}^{|\Omega|}$, write a program to solve Problem *. Plot the recovered image. There are 2 images in the data file, try with mario.m (the smaller one) first. See a7_main.m in the data file for details.

## 2 Bonus part (50 points)

Solve the following
$$\min |\mathrm{Ex}|_{p}+\lambda\left|\mathrm{Sx}-\hat{\mathrm{x}}{\Omega}\right|{q} \text { s.t. } \mathrm{x} \geq 0$$
for $p, q \in{1, \infty}, \lambda \geq 0$ is called regularization parameter. Write a series of programs to solve such problem for different $p, q$, plot these recovered images, compare the recovered image to the one from solving Problem $(*)$.

General hint If you implemented everything correctly, the recovered image should looks like the original clean image.

## CO 327 Deterministic OR Models (Non-Specialist Level)

An applications-oriented course that illustrates how various mathematical models and methods of optimization can be used to solve problems arising in business, industry, and science. [Offered: W,S]

Course ScheduleSpring 2022Winter 2022

CO327 covers a subset of the material from CO370, and covers some additional items (that are not covered in
CO370).
Note: There will be considerable differences between the video-lectures versus what is in the course notes.
Please do NOT use the course notes as a primary information source. The course will vary in many areas from
what is in the course notes and will cover material not in the course notes.
Students are expected to view and study the lecture videos, read the course notes and handouts
(supplements), take notes, and complete all assignments, quizzes, and tests, and to attend the weekly
synchronous tutorials. This course is a continuation of CO 227 (or CO 250). All students are expected to
review material from that course.
Students are expected to spend approximately 10-15 hours per week on this course. This includes viewing the
lecture videos, reading the course notes, constructing and analysing examples and models, attempting and
writing solutions to questions on assignments and quizzes.
Students having any difficulty can consult the instructor via Piazza, and the instructor will set up one-on-one
meetings over Zoom or Microsoft-Teams, as needed.