One loss reveals exact solutions for certain signed rank one problems
One Loss Resolves Signed Rank-One Gradient Fibers: Exact Decoding on Cycle and Theta Blocks
Symbolic Computation
Summary
Sometimes, when trying to figure out a hidden signal from limited clues, there can be multiple possible answers. This paper shows that for particular structured problems, just one well-chosen measurement can uniquely reveal the exact signal, even if the signs of components are unknown. The researchers prove this mathematically for certain patterns called cycles and theta blocks, and provide methods to decode the signal exactly under some conditions. They also explain the complexity behind decoding and when it becomes difficult.
What this means in practice
- •For signal processing engineers: Identify exact signals in structured measurement setups using minimal queries that resolve ambiguities in signed rank-one problems.
- •For network reliability analysts: Use exact decoding techniques on cycle-like network structures to detect and verify failure points with fewer tests.
A theory result. No direct application yet.
Authors
Junwen Lou, Shuo Tian, Penghui Liu
Abstract
For masked rank-one least squares with unrestricted signs, gradients reveal weighted margins and the loss reveals the target's squared norm. We prove that this one scalar resolves the gradient ambiguity on bipartite cycle and length-three parallel-path blocks: every target fixed before sampling and nonzero on cycle edges is identified almost surely by one legal positive query drawn from an absolutely continuous law. On six-cycle flowers, open target and query sets retain $3^r$ bounded gradient candidates. A common algebraic witness excludes cross-block energy cancellation. Cactus masks admit explicit exception certificates and target-uniform finite-grid bounds; theta blocks admit an existence guarantee. For nondegenerate cactus reductions, an exact decoder returns complete actual real lists, with bit cost polynomial in input length, the cycle-degree product $D$ and the optional budget parameter $2^κ$. Energy-coordinate propagation certifies singletons without a product join. The product $D$ can grow exponentially in cycle count. Exponential certificate-degree and output bounds, and weak NP-hardness at a fixed uniform query, characterize distinct costs of exact decoding.