Many signals in radar, sonar, optics and imaging are built from chirps: tones whose frequency rises or falls steadily over time. In an ordinary spectrum a chirp smears across many frequency bins. The fractional Fourier transform rotates the time-frequency plane by an angle $\alpha$, and at the right angle the same chirp becomes a single spike. This suggests a natural compressed-sensing setup. Compressed sensing recovers a signal from far fewer measurements than its length by exploiting the fact that the signal has few nonzero coefficients in some basis. Here we would measure a few random fractional-Fourier coefficients at one angle and recover a signal that is sparse at another angle. Pure mathematics has separately produced uncertainty principles for these transforms. The limit on how concentrated a signal can be in two rotated domains is not a fixed constant as in the Heisenberg case. It shrinks to zero as the two domains approach each other. Our proposal is that this shrinking uncertainty constant is precisely the quantity that sets how many measurements recovery needs. It also sets the extra price paid when the chirp angles are unknown and must be searched over. Theory has never stated that price sharply, and current proofs charge for it with crude logarithmic factors.
The note makes two claims. First, for discretizations of the fractional transform that preserve its continuous geometry, the number of random measurements needed scales like $s\log N/|\sin(\beta-\alpha)|$. Here $s$ is the sparsity, $N$ is the signal length, $\beta$ is the measurement angle and $\alpha$ is the sparsity angle. The factor $|\sin(\beta-\alpha)|$ is exactly the parameter that controls the linear canonical uncertainty floor. Second, when the signal is a mixture of $K$ chirp families at unknown angles, the cost of not knowing the angles should be additive, roughly $K\log N$ extra measurements, rather than the multiplicative inflation produced by a union bound over a grid of candidate angles. The argument uses the uncertainty relation as a distance on the space of angles: nearby angles produce nearly indistinguishable sparse models, so they should not be counted separately.
Why this question, and what is already known
The uncertainty side supplies the key quantity. New Inequalities and Uncertainty Relations on Linear Canonical Transform Revisit proves Heisenberg and entropic inequalities between two linear canonical domains. Linear canonical transforms are the family that contains the fractional Fourier transform as rotations. In those inequalities the lower bound is $|a_1b_2-a_2b_1|^2/4$, which for two rotations reduces to $\sin^2(\alpha_1-\alpha_2)/4$. The bound vanishes when the domains align. Uncertainty principles associated with the offset linear canonical transform gives the support version: a signal concentrated on a set $\Omega$ with transform concentrated on $\Gamma$ must satisfy $|\Omega||\Gamma|\ge 2\pi b(1-\epsilon_\Omega-\epsilon_\Gamma)^2$. In compressed sensing, this kind of support inequality is the seed of a coherence bound. Both papers motivate our work. Neither connects its constant to recovery, and the first explicitly flags that discrete versions break the continuous invariances. That open problem is the one we take up.
The recovery side supplies the method and the target. Unified Theory for Recovery of Sparse Signals in a General Transform Domain proves recovery from $O(\mu s\log N)$ measurements for a general sparsifying transform. Here $\mu$ is the coherence between measurement and sparsity atoms, meaning the largest overlap between any measurement vector and any basis vector. Its proof uses the "golfing" dual-certificate construction, which we reuse. It does not treat fractional kernels, and it does not ask what happens when the transform has unknown parameters. On the Role of Total Variation in Compressed Sensing shows that structure can replace $\log N$ by $\log M\log s$ when discontinuities are separated by $M$, and it states that removing the remaining logarithms is open. That paper constrains our ambitions: we do not claim to remove the $\log N$ that comes from random sampling itself. We only claim to remove the extra cost of searching over angles. The general mechanism for that extra cost is the union bound over a discretized parameter space. The sample-complexity literature identifies this mechanism as a common source of spurious logarithms, for example in Nearly-Tight Bounds for Testing Histogram Distributions.
The fractional-domain side supplies the failure case. Generalized Sampling Theory in the Quaternion Domain: A Fractional Fourier Approach builds Nyquist-type sampling expansions at a single fractional angle. It reports that this approach cannot suppress non-stationary chirped noise, because one angle cannot follow several chirp rates. Fractional Wavelet-Based Generative Scattering Networks shows empirically that fusing fractional orders $\alpha=0.4$ and $\alpha=1.6$ improves CelebA PSNR from 21.16 to 22.07 dB. This is evidence that multiple angles carry complementary information, but the paper offers no guarantee. The quaternion papers, Quaternion Fractional Fourier Transform: Bridging Signal Processing and Probability Theory and Two-dimensional quaternion linear canonical transform: a novel framework for probability modeling, are continuous and theoretical and leave discrete sampling open. They play only a minor role here, for reasons given below.
The obvious idea, and why we do not pursue it
The obvious move at this intersection is to prove an $O(\mu s\log N)$ theorem for a subsampled discrete quaternion fractional Fourier transform. For a single known angle this is close to a relabeling. The common chirp-based discretization multiplies by a chirp, applies a discrete Fourier transform, and multiplies by another chirp. That is a diagonal unitary matrix times a Fourier matrix times another diagonal unitary matrix. Every entry therefore has magnitude $1/\sqrt N$, and recovery is exactly Fourier compressed sensing applied to a dechirped signal. For the common one-sided quaternion transforms, the quaternion structure similarly splits into a pair of complex problems. A theorem of this kind would be correct and uninformative.
The interesting cases are the ones where this reduction fails. One is a discretization that keeps the continuous geometry, such as the Hermite-eigenvector discrete fractional transform, which approaches the identity as the angle goes to zero. The other is a signal that is sparse over several angles that are not known in advance. In the second case no single dechirping operation makes the problem a standard one.
Core Claim
Let $F_\theta$ denote a geometry-preserving discrete fractional Fourier transform at angle $\theta$. Take measurements as $m$ random rows of $F_\beta$ and suppose the signal is $s$-sparse in $F_\alpha$. The coherence is then the largest entry of $F_{\beta-\alpha}$. The continuous kernel of that transform has constant magnitude $1/\sqrt{2\pi|\sin(\beta-\alpha)|}$. This is the same $b$ that appears in the offset linear canonical Donoho–Stark bound. That suggests
$$ \mu(\beta-\alpha)\;\approx\;\frac{c}{\sqrt{N\,|\sin(\beta-\alpha)|}},\qquad m^\star\;\gtrsim\;\frac{s\log N}{|\sin(\beta-\alpha)|}, $$
where $c$ is a discretization constant and $m^\star$ is the number of measurements at which recovery succeeds with high probability. The second expression follows from substituting $N\mu^2$ into the incoherence bound of the unified-theory paper. We expect it to hold away from a boundary layer near $|\sin(\beta-\alpha)|\approx 1/N$, where the discrete kernel stops looking like the continuous one.
For mixtures, suppose the signal is a sum of $K$ components, each $s_k$-sparse at an unknown angle $\alpha_k$, with total sparsity $s=\sum_k s_k$. The conjecture is that
$$ m^\star\;\lesssim\;\frac{s\log N}{\min_{j,k}|\sin(\beta_j-\alpha_k)|}\;+\;C\,K\log N, $$
where the $\beta_j$ are the measurement angles. The naive alternative grids the angles at resolution about $1/N$ and applies a union bound over the roughly $N^K$ resulting models. In standard structured-Fourier proofs, the logarithm of that grid size enters multiplied by the polylogarithmic factors of the restricted isometry argument.
The uncertainty relation is the tool that should make the extra term additive. The quantity $|\sin(\alpha-\alpha')|$ measures how distinguishable the models at angles $\alpha$ and $\alpha'$ are, so it can serve as the distance in a chaining argument over angles. Chaining replaces a single union bound with a sum over increasingly fine scales, so that nearby models are not paid for separately. The vanishing of the same uncertainty bound at aligned angles should give a matching lower bound through Fano's inequality: angles closer than about $1/N$ cannot be told apart, which caps how much angle information the measurements need to carry.
Research Program
The work has three parts, which feed one another.
The first part is the discrete operational link. We will compute the coherence of the Hermite-eigenvector and chirp-based discrete transforms exactly, across angles and for $N$ from 128 to 4096. We will then prove a discrete Donoho–Stark inequality whose constant is explicit in $|\sin\theta|$, including the boundary layer near alignment. This directly addresses the continuous-to-discrete gap that the linear canonical uncertainty literature leaves open.
The second part is the unknown-angle theory. We will adapt the golfing construction from Unified Theory for Recovery of Sparse Signals in a General Transform Domain to a union of $K$ fractional bases, using chaining over angle space with the uncertainty-derived distance. We will pair the resulting upper bound with a Fano lower bound built from near-aligned angle pairs. If chaining cannot achieve an additive cost, the lower-bound construction should show why. Either result settles whether this particular polylogarithmic gap is real.
The third part is measurement design. A single measurement angle has blind directions: any $\alpha_k$ near $\beta$ inflates the sample count by the factor $1/|\sin|$. We will analyze spreading the measurements over $J$ random angles and characterize the smallest $J$ that bounds $\min_{j,k}|\sin(\beta_j-\alpha_k)|$ away from zero for every possible configuration of chirp angles.
Baselines
The naive reference point is uniform random Fourier subsampling, followed by $\ell_1$ recovery in an ordinary Fourier or wavelet basis that ignores chirp structure. It shows how much the smearing of chirps costs. We run it on identical signals at identical measurement counts, using the same solver and the same tolerance.
The strongest reduction baseline is oracle dechirping. The true angles are revealed, the signal is demodulated, and standard Fourier compressed sensing is applied. For a single known angle with chirp-based discretization, this is exactly the right method. It is also the ceiling that any unknown-angle method must approach. Beating it is impossible by construction. Our claim is met if our method's phase-transition sample count is within an additive $O(K\log N)$ of the oracle's.
The strongest existing method for an operator with unknown parameters is joint alternating minimization over the operator parameters and the sparse code. This follows Signal Recovery in Perturbed Fourier Compressed Sensing, which reports RRMSE of 4–6% on 2D Shepp-Logan and brain MRI experiments, against more than 80% for a Taylor-linearized baseline. In our setting it alternates between the $\ell_1$ code and the angle estimates $\alpha_k$. We give it the same number of solver iterations and the same initialization grid as our method. Beating it means a lower phase-transition $m^\star$ at matched RRMSE, or a lower RRMSE at matched $m$ in the regime where chirp angles fall within $0.1$ radians of the measurement angle. That is the regime where we predict alternating minimization stalls. It has no published number on chirp mixtures, and we found no reported result on Lacuna for fractional-domain compressed sensing on any benchmark.
The grid-plus-union-bound baseline is $\ell_1$ recovery over a dictionary that concatenates fractional bases at $L$ gridded angles. It isolates the key ingredient. If its empirical $m^\star$ grows only additively in $\log L$, the chaining argument is explaining something practitioners already get for free, and the contribution narrows to theory. A further ablation fixes the measurement angle $\beta$ to a single value instead of spreading it over $J$ angles, which isolates the blind-direction effect. For the chirped-noise task we also include the single-angle sampling expansion of Generalized Sampling Theory in the Quaternion Domain: A Fractional Fourier Approach. That paper reports only "stabilizing" MSE and no absolute figure.
Why not just…?
Why not just dechirp and use ordinary Fourier compressed sensing? For one known angle under chirp-based discretization, this is exactly correct, and the experiments include it to show that equivalence numerically. It fails in two cases. With several angles, no single demodulation sparsifies the whole signal. With geometry-preserving discretizations, the coherence is not $1/\sqrt N$. The angle-sweep experiment shows where the two discretizations diverge.
Why not just grid the angles and run ordinary $\ell_1$ on the concatenated dictionary? This is the real threat. It may work well in practice, and if its sample count grows additively in the grid size, our algorithmic claim disappears and only the theoretical claim remains. The grid-size sweep below decides this. A dense grid also makes the dictionary highly coherent, since adjacent angles nearly coincide. The uncertainty-based analysis predicts this hurts once grid spacing falls below about $1/N$, and that prediction is directly checkable.
Why not use short-time Fourier or wavelet dictionaries, which already localize in time and frequency? Their fixed tilings spread a linear chirp over many atoms, which inflates the effective sparsity. The fractional-wavelet fusion gains reported in Fractional Wavelet-Based Generative Scattering Networks are indirect evidence for this. We measure it directly by comparing effective sparsity and $m^\star$ against a matched short-time Fourier dictionary.
Why not treat multichannel signals as independent or jointly sparse real channels instead of quaternions? We expect group-sparse recovery over real channels to match quaternion recovery for one-sided transforms. That is why quaternions are not central here. We run a single test on three-channel chirp mixtures with a shared support, and we will report any quaternion advantage only if it exceeds group-sparse $\ell_{2,1}$ recovery at matched $m$.
Proposed Experiments
The first decisive check is the angle sweep. Using synthetic $s$-sparse signals in a fractional basis with $N=512$, matching the length of the TV paper's 1D test signals, we will sweep $\beta-\alpha$ from $10^{-3}$ to $\pi/2$ under both discretizations and record the 50% success threshold $m^\star$. The prediction is that $m^\star\cdot|\sin(\beta-\alpha)|$ stays flat for the geometry-preserving transform and that $m^\star$ itself stays flat for the chirp-based one. A clearly different scaling under the geometry-preserving transform would falsify the operational link.
The second check is the mixture and grid sweep. For chirp mixtures with $K\in\{1,2,4,8\}$ unknown angles, we plot $m^\star$ against $K$ and against the grid size $L$ for every method. The additive conjecture predicts slopes in $\log L$ close to the oracle's, offset by about $K\log N$. Multiplicative growth would vindicate the union bound and send us to the lower-bound side of the program.
For imaging, we measure the $256\times256$ Shepp-Logan phantom and the $512\times512$ USAF-1951 chart through 2D fractional transforms at one or several angles, with total-variation recovery. We compare against the 4–6% RRMSE level that the alternating-minimization method reaches on Shepp-Logan under its own perturbation model. This is a reference point, not a matched comparison.
The chirped-noise test reproduces the setting where the single-angle sampling expansion fails: multi-chirp noise added to a bandlimited signal. We ask whether multi-angle compressive recovery with $J$ random measurement angles removes the noise at a measurement count our bound predicts.
Each configuration is run over 50 random draws. We report RRMSE and success curves as the primary metrics.
References
- New Inequalities and Uncertainty Relations on Linear Canonical Transform Revisit
- Uncertainty principles associated with the offset linear canonical transform
- Unified Theory for Recovery of Sparse Signals in a General Transform Domain
- On the Role of Total Variation in Compressed Sensing
- Nearly-Tight Bounds for Testing Histogram Distributions
- Generalized Sampling Theory in the Quaternion Domain: A Fractional Fourier Approach
- Fractional Wavelet-Based Generative Scattering Networks
- Quaternion Fractional Fourier Transform: Bridging Signal Processing and Probability Theory
- Two-dimensional quaternion linear canonical transform: a novel framework for probability modeling
- Signal Recovery in Perturbed Fourier Compressed Sensing