In signal processing and imaging, we frequently encounter inverse problems where the relationship between the hidden signal and our observations is non-linear. A classic example is phase retrieval: sensors like photodetectors or X-ray cameras can only record the intensity (magnitude) of a light wave, completely losing the phase information. Another example is blind deconvolution, where we observe the convolution of two unknown signals—such as a message distorted by an unknown communications channel.
Mathematically, these problems force us to solve systems of quadratic or bilinear equations. Standard optimization techniques struggle here because the solution space is highly non-convex, riddled with local minima that trap gradient descent algorithms.
Matrix lifting is a powerful mathematical strategy that resolves this non-convexity. By mapping the problem into a higher-dimensional matrix space, non-linear vector constraints become linear matrix constraints, allowing us to solve notoriously difficult problems with global convergence guarantees.
The Core Intuition: Turning Quadratic into Linear
To understand why lifting works, let us look at the geometry of a phase retrieval measurement. Suppose we want to recover an $n$-dimensional complex signal vector $x \in \mathbb{C}^n$. We collect a series of magnitude-only measurements $b_i$:
$$b_i = |a_i^* x|^2$$
where $a_i^*$ is the conjugate transpose of a known measurement vector $a_i$. The constraint $|a_i^* x|^2 = b_i$ defines a non-convex hypersurface (a hyper-sphere or a pair of parallel planes) in the vector space of $x$. Finding an intersection of many such hypersurfaces is an NP-hard combinatorial puzzle.
However, we can rewrite the quadratic term using a basic property of linear algebra. Notice that:
$$|a_i^* x|^2 = (a_i^* x)(x^* a_i) = a_i^* (x x^*) a_i$$
Now, let us introduce a new variable, a matrix $X = x x^*$. The matrix $X$ is an $n \times n$ rank-1, positive semidefinite matrix that represents the outer product of the signal with itself. Using the trace cyclic property, we can rewrite the measurement equation as:
$$b_i = \text{Tr}(a_i^* X a_i) = \text{Tr}(a_i a_i^* X)$$
If we define a known measurement matrix $A_i = a_i a_i^*$, the equation becomes:
$$\text{Tr}(A_i X) = b_i$$
Look at what just happened: the relationship between our measurement $b_i$ and the new variable $X$ is completely linear. By "lifting" our search space from the $n$-dimensional vector $x$ to the $n \times n$-dimensional matrix $X$, we have straightened out the curved, non-convex measurement constraints into flat, linear hyperplanes.
The Convex Relaxation Step
While the measurement constraints are now linear, we haven't completely escaped non-convexity. For $X$ to perfectly represent our original vector $x$, it must satisfy two conditions:
- It must be positive semidefinite ($X \succeq 0$).
- It must be exactly rank-1 ($\text{rank}(X) = 1$).
The positive semidefinite constraint is convex—it forms a nice, clean cone. However, the rank-1 constraint is highly non-convex.
The breakthrough of the matrix lifting framework, pioneered in works like PhaseLift by Vladislav Voroninski and later analyzed by Emmanuel J. Candès et al., is to simply drop the rank constraint. This process is called convex relaxation.
Instead of searching for a rank-1 matrix, we solve a Semidefinite Program (SDP) that minimizes the trace of $X$ (which acts as a convex proxy for minimizing rank, akin to $L_1$ minimization in compressive sensing):
$$\begin{aligned} \text{minimize} \quad & \text{Tr}(X) \\ \text{subject to} \quad & \text{Tr}(A_i X) = b_i, \quad i = 1, \dots, m \\ & X \succeq 0 \end{aligned}$$
As demonstrated by Henrik Ohlsson et al. in the CPRL framework, if we have a sufficient number of measurements, the unique optimal solution to this convex program is guaranteed to be the exact rank-1 matrix $X = xx^*$ corresponding to our true signal. Once $X$ is found, we can recover $x$ via a simple top-eigenvector decomposition.
Vector Space (Non-Convex) Matrix Space (Convex Relaxation)
Quadratic Constraints Linear Constraints + PSD Cone
\ / /==============/
\ xx* / / Linear /
\ / / Hyperplane /
__________\__/__________ /==============/
Local Minima Traps Global Optimum Guaranteed
Generalizing to Bilinear Systems
The beauty of matrix lifting is that it is not limited to phase retrieval. It applies naturally to any problem dominated by bilinear interactions, where we observe the product of two unknown vectors, $h$ and $x$.
In blind deconvolution or blind channel identification, our measurements can often be framed as linear combinations of the elements of an outer product matrix $X = hx^*$. As explored by Michael B. McCoy et al., lifting maps these non-linear vector interactions into a linear demixing framework.
For instance, Santiago Segarra et al. applied this to the blind identification of graph filters, treating the interaction between an unknown network process and an unknown sparse input signal as a single low-rank matrix recovery task. Similarly, Ali Ahmed 0004 et al. demonstrated that combining matrix lifting with positive semidefinite constraints allows for the simultaneous resolution of blind deconvolution and phase retrieval, finding global solutions in domains that were previously considered computationally intractable.
Bypassing the Matrix Explosion: Non-Lifting Alternatives
If matrix lifting is so powerful, why isn't it used for every non-linear inverse problem? The answer comes down to computational complexity.
Lifting an $n$-dimensional vector to an $n \times n$ matrix explodes the number of variables quadratically. If you are trying to reconstruct a modest 1-megapixel image ($n = 10^6$), the lifted matrix $X$ requires $10^{12}$ entries—demanding terabytes of memory just to store the variable.
To combat this dimensionality curse, researchers developed natural domain convex relaxations that achieve the benefits of convexity without ever leaving the original vector space.
A prominent example is PhaseMax, introduced by Christoph Studer et al. Instead of lifting the problem, PhaseMax utilizes an anchor vector—an initial rough guess of the signal's direction (which can be obtained via simple spectral initialization methods).
By maximizing the alignment (inner product) of the estimated signal with this known anchor vector, subject to convex magnitude inequality constraints derived from the measurements, the authors show that exact signal recovery is possible directly in the original signal dimension.
As detailed by Tom Goldstein et al. in Convex Phase Retrieval without Lifting via PhaseMax, this anchor-based linearization cuts memory requirements from quadratic to linear ($O(n)$), bridging the gap between the theoretical guarantees of matrix lifting and the scalability demands of real-world, high-resolution engineering applications.
Key Foundational Work
Spaceability of Functions with Complicated Quantization and Truncation Behavior (2012) — contributed 2 concept elements to this direction.
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming (2012) — contributed 2 concept elements to this direction.
CPRL -- An Extension of Compressive Sensing to the Phase Retrieval Problem (2012) — contributed 1 concept elements to this direction.