Abstract
The Frank-Wolfe (FW) algorithm has been widely
used in solving nuclear norm constrained problems,
since it does not require projections. However, FW
often yields high rank intermediate iterates, which
can be very expensive in time and space costs for
large problems. To address this issue, we propose
a rank-drop method for nuclear norm constrained
problems. The goal is to generate descent steps that
lead to rank decreases, maintaining low-rank solutions throughout the algorithm. Moreover, the optimization problems are constrained to ensure that
the rank-drop step is also feasible and can be readily incorporated into a projection-free minimization
method, e.g., FW. We demonstrate that by incorporating rank-drop steps into the FW algorithm, the
rank of the solution is greatly reduced compared to
the original FW or its common variants.