Q11 2018

Hi,
how can the computational cost of LMO and projection linked to SVD and top singular value? Also can we always say that the cost of projection > cost of LMO or is only >=?
Thank you.

Top comment

The common examples of constrained optimization we see in the course are like Lasso regression which minimizes over a convex set in the vector space, e.g. \(\|x\|_1 \le 1\). In this question, we are considering an optimization problem over a matrix space where the constraint is defined by the matrix norm. The matrix norm can be computed using the singular values of the matrix, checkout the wikipedia page. Therefore SVD and top singular value is need to evaluate the matrix norm. You can find details of the solution in exercise 8.

As for the costs, it is not easy to simply state that projection is > or >= LMO. For example, if we already know the input is inside the constraint, then the projection is the identity function which is faster than LMO.

Page 1 of 1

Add comment

Post as Anonymous Dont send out notification