(“Screened Poisson smoothing”) Suppose we sample a function f(x) at n positions x 1 , x 2 , . . . , x n , yielding a point  ≡ (f(x 1 ), f(x 2 ), . . . , f(x n )) ∈ R n . Our measurements might be...

(“Screened Poisson smoothing”) Suppose we sample a function f(x) at n positions x₁, x₂, . . . , x_n, yielding a point
 ≡ (f(x₁), f(x₂), . . . , f(x_n)) ∈ R
ⁿ. Our measurements might be noisy, however, so a common task in graphics and statistics is to smooth these values to obtain a new vector
 ∈ R
ⁿ.

(a) Provide least-squares energy terms measuring the following: (i) The similarity of
 and
. (ii) The smoothness of
. Hint: We expect f(xi₊₁) − f(x_i) to be small for smooth f.

(b) Propose an optimization problem for
 using the terms above to obtain
, and argue that it can be solved using linear techniques.

(c) Suppose n is very large. What properties of the matrix in 4.13b might be relevant in choosing an effective algorithm to solve the linear system?