CS395T: Numerical Optimization for Graphics and AI:
Homework I
1 Guideline
Please complete 6 problems out of 14 problems. It is required to choose at least one problem from
each section, i.e., Linear Algebra, Probability, Geometry/Topology.
You are welcome to complete more problems.
2 Linear Algebra
Notations. A 0 means A is positive semide nite, i.e., A is symmetric and all its eigenvalues are non-
negative. kAkdenotes the spectral norm, i.e., the maximum singular value of A. Given a symmetric matrix
X, we use 1(X) n(X) to denote its eigenvalues in the decreasing order.
Problem 1. The exponential map for a square matrix A is given by
Suppose A 0. Then
kAk kA11k+kA22k:
Problem 3. Let be the entry-wise product operator. Namely, given two matricesA = (aij)1 i n;1 j m;B =
(bij)1 i n;1 j m2Rn m, A B = (aijbij)1 i n;1 j m. Show that
kA Bk kAk kBk:
Problem 4. Given a square X2Rn n. We de ne the projection operatorPO(m)( ) : Rn n!O(m) to the
space of orthogonal matrix as follows
PO(m)(X) = UVT; X = U VT;
X = U VT is the singular value decomposition. Given a square matrix X2Rn n. Suppose there exists a
orthogonal matrix R such that
kX Rk 13:
Then
kPO(m)(X) Rk + 2:
Problem 5. Let A;N2Rn n be two symmetric matrices. The Wely’s inequality tells us that
j 1(A+N) 1(A)j kNk:
Here we are looking for a much tight bound between 1(A+N) and 1(A). Denote u as the top-eigenvector
of A, i.e., kuk= 1 and Au = 1(A)u. Suppose
1(A) 2(A) kNk+juTNuj:
Then
juTNuj 1(A+N) 1(A) juTNuj+ kNk
2 juTNuj2
1(A) 2(A) :
3 Probability
Problem 6. Four points are chosen on the unit sphere. What is the probability that the origin lies inside
the tetrahedron determined by the four points?
Problem 7. You have n> 1 numbers 0; ;n 1 arranged on a circle. A random walker starts at 0 and at
each step moves at random to one of its two nearest neighbors. For each i, compute the probability pi that,
when the walker is at i for the rst time, all other points have been previously visited, i.e., that i is the last
new point. For example, p0 = 0.
Problem 8. Let X be a random positive semide nite matrix, and let A be a xed positive de nite matrix.
Then, 8A,
Pr[X A] Tr(E(X)A 1):
Here X A means X A is positive semide nite.
Problem 9. Let xi2R;1 i n be independent random variables that satis es
E(xi) = 0; jxij 1:
Find the smallest possible constant c such that
Problem 10. Suppose we choose a permutation of the ordered set N =f1;2; ;nguniformly at random
from the space of all permutations of N. Let L( ) denote the length of the longest increasing subsequence
in permutation .
For large n and some positive constant c, prove that E[L( )] cpn.
Derive a upper bound on E[L( )].
Derive a concentration bound on L( ), namely, determine f1(n) and f2(n) so that f1(n) E[L( )]
f2(n) with high probability.
4 Geometry and Topology
Problem 11. Consider multiple points in an Euclidean space. The maximum pairwise distance is upper
bounded by 2. Determine a tight bound on the radius of the enclosing ball of these points.
Problem 12. We color each edge of a maximally connected planar graph with one of three colors such that
each face (triangle) has all three colors in its boundary.
Show that a 4-coloring of the vertices implies a 3-coloring of the edges.
Show that a 3-coloring of the edges implies a 4-coloring of the vertices.
Problem 13. Consider orthogonal matricesR2O(m);det(R) = 1. Collect its diagonal entriesR11; ;Rmm
into a vector in Rm. Prove that the convex hull of these vectors is equivalent to the convex hull of points
( 1; ; 1) with a odd number of 1.
Problem 14. We have covered how to estimate the best rigid transformation between a pair of point clouds.
Here we study the consistency of such pair-wise transformations among multiple point clouds. Consider n
point clouds P = fP1; ;Png. Each point cloud consists of m points i.e., Pi = (pi1; ;pim) 2 Rl m,
where l is the dimension of the ambient space. We assume that points pij;1 i n for each xed j
are in correspondence. With this setup, we denote the optimal rigid transformation from Pi and Pj as
Tij = (Rij;tij). As we have learned in class, Rij and tij admit a close-form. solution via singular value
decomposition.
Now we consider the consistency of these rigid transformations among multiple point clouds. For each
triple of point clouds Pi;Pj;Pk, we say the pair-wise rigid transformations Tij = (Rij;tij),Tjk = (Rjk;tjk)
and Tki = (Rki;tki) are consistent if Tki Tjk Tij = Id or in other words
RkiRjkRij = Il
RkiRjktij +Rkitjk + tki = 0 (1)
We say P is regular if the pair-wise transformations are consistent among all triples 1 i j k n.
In general, if you form. P by sampling point clouds randomly, P is not regular. So this problem is to study
under what conditions P is regular:
Derive the condition for l = 2, n = 3 and m = 3.
Derive the su cient conditions for other con gurations of l,m,and n.