Many fundamental problems in signal processing and computer vision—such as phase retrieval, blind deconvolution, and system identification—are inherently non-convex. Traditionally, these problems were solved using heuristic iterative algorithms that often lacked global convergence guarantees. A major breakthrough occurred with the introduction of lifting, a technique that transforms these difficult non-convex problems into higher-dimensional convex ones, typically semidefinite programs (SDPs).
However, this mathematical elegance comes at a steep price: a quadratic explosion in dimensionality. As researchers move toward high-resolution imaging and massive data systems, the computational and memory overhead of lifting has become the primary bottleneck for the field.
The Intuition Behind Lifting
The core difficulty in problems like phase retrieval is the presence of quadratic constraints. For a signal $x \in \mathbb{C}^n$, we often only measure intensities $b_i = |a_i^* x|^2$. This relationship is non-convex in $x$.
Lifting resolves this by reimagining the vector $x$ as a rank-one matrix $X = xx^*$. Under this transformation, the quadratic measurement becomes a linear one: $$b_i = \text{Tr}(a_i a_i^* X)$$ By relaxing the requirement that $X$ must be rank-one to the convex constraint that $X$ must be positive semidefinite ($X \succeq 0$), the problem becomes a convex SDP. As Candès et al. demonstrated with PhaseLift, this approach provides a robust, mathematically principled way to recover signals with provable guarantees. Similar lifting strategies have been applied to blind identification by Ohlsson et al. and to nonlinear basis pursuit by Yang et al..
The Scalability Wall
While lifting provides theoretical reliability, it suffers from the "curse of dimensionality." Transforming an $n$-dimensional vector into an $n \times n$ matrix increases the number of variables from $O(n)$ to $O(n^2)$.
For a megapixel image, $n = 10^6$, meaning the lifted matrix $X$ would contain $10^{12}$ entries. This quadratic growth makes standard convex solvers computationally prohibitive for high-resolution scientific imaging, such as the 3D datasets discussed by Fannjiang and Strohmer. The authors of CPRL note that this memory overhead restricts convex methods to small-scale signals, while Ahmed et al. highlight that the bottleneck is particularly acute in blind deconvolution, where the number of elements grows with the product of the lengths of the two unknown signals.
Strategies for Scaling Convexity
To bridge the gap between theoretical guarantees and practical feasibility, researchers have developed several strategies to bypass or optimize the lifting process.
1. Lifting-Free Convexity
The most direct way to avoid the $O(n^2)$ bottleneck is to find convex relaxations that operate in the original $n$-dimensional space. Studer and Goldstein introduced PhaseMax, which uses a linear objective and an "anchor" vector to achieve exact recovery without lifting. By maximizing the signal's projection onto an initial guess, PhaseMax maintains the benefits of convexity while requiring only linear memory. Subsequent work by Salehi et al. proved that regularized versions of this approach can achieve optimal sample complexity.
2. Structural Discretization
Another approach involves reducing the number of variables by exploiting the underlying structure of the data. Geiping et al. proposed using graph discretizations, such as superpixels, to solve functional lifting problems. By replacing pixel-based grids with smarter spatial representations, they achieved significant reductions in runtime and memory with minimal loss in accuracy.
3. Leaner Relaxations
In communication systems, where real-time performance is critical, researchers have sought leaner alternatives to SDPs. Zhao et al. developed a sparse quadratic programming relaxation for MIMO detection that shifts from matrix-based relaxations to vector-based formulations, drastically reducing overhead for 5G "Massive MIMO" systems. Similarly, Aghasi and Ahmed proposed $\ell_1$-BranchHull, which solves bilinear inverse problems in the natural parameter space rather than a lifted one.
The Role of Non-Convex Refinement
When lifting is too expensive, an alternative is to return to non-convex optimization but with better initialization and analysis. Algorithms like Wirtinger Flow, analyzed by Dong and Shi, and the Majorization-Minimization framework used in PRIME by Qiu et al., offer low-complexity updates that scale linearly. These methods often serve as a middle ground: they lack the universal global optimality of lifted SDPs but are practically viable for the massive datasets generated by modern sensors.
Key Foundational Work
CPRL -- An Extension of Compressive Sensing to the Phase Retrieval Problem (2012) — contributed 2 concept elements to this direction.
Total variation for cyclic structures: Convex relaxation and efficient minimization (2011) — contributed 1 concept elements to this direction.