Data in the real world often lives on curved spaces, not flat plains. Colors sit on a circle of hues, orientations spin like tops, and even statistical summaries can trace hyperbolic surfaces. Denoising such data with standard tools is like trying to clean a watercolor painting with a straightedge: you miss the edges that matter because the space itself bends. A new wave of methods has started to treat these shapes with care, turning non-convex geometries into problems that can be solved with the familiar machinery of convex optimization.
A team at Technische Universität Berlin, led by Robert Beinert and Jonas Bresch, extends a promising trick: embed the non-convex manifold data in a Euclidean ambient space and encode the hard constraints with a stack of positive semi-definite matrices, then relax the rank to get a convex problem. The paper applies this to two new data families—multi-binary signals like multi-color QR codes and Stiefel-valued data that capture orthonormal bases—and shows the approach can recover clean signals with standard solvers. It’s a step toward making the math of curved data as approachable as solving ordinary images.
Denoising Multi-Binary Data on Graphs
Multi-binary data live in a space that looks like a high-dimensional cube: Bd = {−1, 1}^d. Think of a color-coded QR code that encodes information not with a single black square but with a triad of color channels. If you scale and shift the RGB cube appropriately, the color modules fit into Bd. In other words, you’re trying to restore a patchwork of red, green, and blue components that each take only two values, all while the signal sits on a graph that encodes which pixels touch or relate to which other pixels.
To denoise such a signal you might write a classic energy: a data fidelity term that punishes deviation from the observed noisy colors, plus a total variation term that favors piecewise constant regions. But the domain is non-convex, so the optimization is hard and sometimes intractable. The innovation here is to replace the hard, jagged domain with its convex hull—the cube [−1, 1]^d—and to rewrite the objective in a way that makes it convex. The key move is to replace the binary norm term with a linear inner product against the observed data, and to add the TV term as before, only now the optimization happens over the full cube rather than a sharp set of corners.
Mathematically, the authors show that this convexified problem is still faithful to the original. They define a transfer Xη that slices the decision variable xn along each coordinate and maps it back into Bd. A coarea-like formula ties the L1 distance in the ambient space to an average of L1 distances after this mapping. In plain terms: solving the convexified version doesn’t just give a nice average solution; for almost every choice of the slicing, you can convert that solution back into a genuine BD-valued solution that solves the original non-convex problem.
The resulting recipe is implemented with the Alternating Direction Method of Multipliers, a workhorse for large-scale convex problems. The projection step is straightforward—each pixel is nudged back into the [-1, 1]^d cube—while the TV subproblem benefits from fast, coordinate-wise updates. The paper’s demonstration on a 20-by-20 multi-color QR code, corrupted by substantial Gaussian noise on a finer grid, is striking: the denoiser recovers a faithful BD-valued image, and in many regions it hits the color values exactly. It’s a vivid reminder that convex relaxations can survive the leap from theory to practice, even for discrete, color-rich data.
Stiefel-Valued Data Denoising
Not all data live on a simple cube. Some wear the geometry of a Stiefel manifold, which is the collection of all orthonormal k-vectors in R^d arranged as columns of a matrix X ∈ R^{d×k}. Put differently: X encodes a moving, living basis for a subspace, and you care about the directions and their orthogonality more than any individual coordinate. This kind of data shows up in image and video recognition tasks where the orientation of a feature matters, or in any setting where you’re tracking a rotating object or a directional field.
The non-convex TV model for Stiefel-valued data mirrors the intuition for the binary case: you want X to stay on the Stiefel manifold while you smooth or denoise. The direct optimization is hard because the constraint X ∈ Vd(k) is non-convex. The twist here is to lift the problem into a convex surrogate by packing each Xn into a larger, positive semi-definite matrix Vn that encodes both the orthogonality and the norm constraint. If you insist rk(Vn) = d, you can recover a genuine orthonormal Xn later; but you can drop the rank constraint to obtain a tractable convex problem on the ambient space and then pull back a valid solution.
Two technical lemmas spell out the exact equivalence: one shows that having Vn PSD with rk(Vn) = d captures the orthogonality structure, and the other links PSD with the norm bound ∥Xn∥2 ≤ 1. With these in hand, the paper writes a convexified TV model: minimize the data-fit plus a TV term, subject to ∥Xn∥2 ≤ 1 for all nodes. The optimization rides on ADMM again, splitting the objective from the PSD-cone constraint and alternating between updating the X variables and projecting onto the unit ball of matrices. It’s a clever dance that keeps the problem in the land of convex solvers while still respecting the geometry of rotation and orientation.
There’s a companion Tikhonov-style denoiser for smooth Stiefel-valued signals. Here, the authors introduce auxiliary variables to track pairwise inner products L(n,m) = Xn^T Xm and recast the non-convex side constraint into a convex, PSD-constrained problem. The ADMM steps again navigate between updating the X’s and projecting onto the PSD cone, with a final projection that enforces the orthogonality structure through an eigenvalue adjustment. The upshot is that a noisy collection of oriented frames or basis vectors can be smoothed into something that really behaves like a valid, near-orthonormal frame across the whole dataset.
From QR Codes to Real-World Signals
The authors don’t stop at abstract math. They show the approach works on tangible data: multi-color QR codes that fuse three independent black-and-white codes into a single color image. The code is a playful testbed for a problem that’s both practical (error resilience in reading codes) and conceptual (how to keep color-channel constraints coherent during restoration). The experiments demonstrate that after denoising with the convexified TV model, the colors align with the intended BD values, even when the input was riddled with noise on a fine grid. The restoration is not merely visually appealing; it preserves the discrete color structure that makes QR codes scannable in the first place.
Beyond the codes themselves, the paper’s Stiefel experiments push the idea further. A synthetic V3(2) signal—two orthonormal vectors in three dimensions per node—was distorted by realistic directional noise and then reassembled. The convexified TV and Tikhonov methods recovered almost perfectly orthonormal bases, with the column norms clinging to one and the pairwise inner products collapsing toward zero. In other words, the methods didn’t just blur the data; they gently nudged it back toward its geometric truth, preserving the very structure that makes these signals meaningful for recognition tasks.
It’s easy to overlook how small, technical advances in denoising can ripple outward. Here the trick is to take non-convex constraints—whether a binary hypercube, a constellation of orthonormal vectors, or a rotating frame—and recast them into a convex problem that standard solvers can chew through efficiently. The authors implement the algorithms in Python and release code on GitHub, lowering the barrier for researchers and practitioners to try the method on their own data. In a world where data grows noisier and more complex, such practical bridges between theory and software matter a lot.
What does this all mean for the future of data processing? At a glance, it isn’t a claim that all physics-ready geometry becomes easy to solve. It is a practical blueprint: when your data live on a non-convex manifold, you can construct a convex surrogate that is provably tight—so you don’t trade global optimality for tractability. In fields as varied as color restoration, computer vision, and robotics, that combination can unlock more robust denoising, faster experimentation, and cleaner signals to feed into higher-level tasks like segmentation, recognition, or control. The work of Beinert and Bresch at Technische Universität Berlin is part of a broader move to bring the elegance of convex optimization to the messy beauty of real-world data geometry.
