PSYCH 221 FINAL PROJECT

Both of the convex optimization techniques discussed below, L1 Norm Minimization and L2 Norm Minimization, try to fill-in the missing pixels in the image in order minimize the measure of total roughness. What varies between them is that how they define that measure of roughness. As the names imply, the former takes roughness to be the L1 norm between neighboring images and the latter takes it to be the L2 norm. These methods only alter the unknown pixels, leaving the others intact. For each pixel, these methods compute the respective norm of the difference of the given pixel with the pixel to the left and top, and sum these norms. It then tries to minimize this sum by varying the values of the unknown pixels. Since, the variables are taken to be the unknown pixels this algorithm cannot modify the contents of theses pixels. Below is a more in-depth analysis of each of the algorithms

L1 Norm Minimization

Below is the L1 Norm function that we are trying to minimize. U represents the image matrix we are trying to minimize. A major attribute of the L1 norm is that it ends up making majority of the pixels that it is filling in the same as either one if its neighbors. Hence, it is usually better when the image contains sharp edges (e.g. image of a text file), and does not perform well on continuous images (e.g. natural images.)

L2 Norm Minimization

Below is the L2 Norm function that we are trying to minimize. Again, U represents the image matrix we are trying to minimize. As opposed to L1 norm, L2 norm has a smooth transition between known and unknown pixels. Hence, L2 norm minimization ends up low pass filtering the image. This works well with natural images; however, does not perform well with images with sharp transitions, i.e. high frequency components.

Norm Minimization Example

A study of interpolation using norm minimization can be seen below. Below are four instances of an image, the first one is uncorrupted, the second one with shot noise, the third one with L2 Norm minimization reconstruction and the last one with L1 Norm minimization reconstruction. As can be seen, the original image has fairly sharp transitions, thus we would expect L1 Norm reconstructions to work better, and the results corroborate our expectations.

Solving the Optimization Problem
Both of these algorithms utilize a convex optimization package called cvx, that can be installed from inside MALAB. Although we have used cvx for these optimization problems, we could have easily implemented off-the-shelf optimization algorithms such as logarithmic barrier method using Newton’s method for solving these optimization problems. The major advantage of using cvx was that it saves us from building our own customized methods for this optimization problem. However, a downside was the computation speed, which was relatively small given the interpreting overhead that cvx has while converting the supplied problem into a form it can use.