  We propose and study a class of novel algorithms that aim at solving bilinear
and quadratic inverse problems. Using a convex relaxation based on tensorial
lifting, and applying first-order proximal algorithms, these problems could be
solved numerically by singular value thresholding methods. However, a direct
realization of these algorithms for, e.g., image recovery problems is often
impracticable, since computations have to be performed on the tensor-product
space, whose dimension is usually tremendous. To overcome this limitation, we
derive tensor-free versions of common singular value thresholding methods by
exploiting low-rank representations and incorporating an augmented Lanczos
process. Using a novel reweighting technique, we further improve the
convergence behavior and rank evolution of the iterative algorithms. Applying
the method to the two-dimensional masked Fourier phase retrieval problem, we
obtain an efficient recovery method. Moreover, the tensor-free algorithms are
flexible enough to incorporate a-priori smoothness constraints that greatly
improve the recovery results.
