Many methods for filling in missing pixels of a color video work the same way. They apply a fixed transform along the time axis, usually the Fourier transform. They then require each transformed "slice" (one frequency's worth of the video, a single matrix) to be low-rank, meaning it can be written as a product of two thin matrices. The transform choice decides what "low-rank video" means. With no transform, every frame must be simple on its own. With the Fourier transform, the video must be simple in a periodic, frequency-by-frequency sense.
The fractional Fourier transform is a family of unitary transforms indexed by one angle $\alpha$. It interpolates between these two extremes: $\alpha=0$ is the identity and $\alpha=\pi/2$ is the ordinary Fourier transform. Intermediate angles rotate the time-frequency plane so that signals whose frequency drifts over time (chirps) concentrate their energy instead of smearing. We propose to treat $\alpha$ as a rank-controlling knob for quaternion video completion. A quaternion is a four-part number whose three imaginary parts hold the red, green and blue values of a pixel together, rather than as three separate channels.
Once the video is transformed along time, the slice-wise factorizations become independent problems. They can all be updated at the same moment on parallel hardware, rather than one after another. That independence is what makes it cheap to sweep a whole path of angles and pick the best one on held-out pixels.
Core Claim
The claim has two parts, each testable.
The first part concerns quality. For color video whose temporal structure is non-stationary (zooms, accelerating pans, slowly drifting illumination), some interior fractional angle gives a transformed tensor with markedly lower effective rank than either endpoint. Completion at that angle should beat both the identity-transform model and the Fourier-transform model from the same code.
The second part concerns cost. Selecting that angle adds almost nothing to the price of a single completion. The reason is that, for fixed $\alpha$, a standard splitting makes the slice problems genuinely separable. Each slice's factor pair can then be solved simultaneously, and solutions at neighboring angles are close enough to warm-start one another.
We state the objective once. Let $\mathcal{Y}$ be the observed quaternion video, $\Omega$ the set of observed entries, and $F_\alpha$ the discrete unitary fractional Fourier matrix of angle $\alpha$ applied along the time mode. The model is
$$\min_{\alpha,\;\{\mathbf{A}_k,\mathbf{X}_k\}} \;\sum_{k} \tfrac12\big(\|\mathbf{A}_k\|_F^2+\|\mathbf{X}_k\|_F^2\big) \quad \text{s.t.}\quad P_\Omega\!\big(F_\alpha^{-1}\times_3 [\mathbf{A}_k\mathbf{X}_k]_k\big)=P_\Omega(\mathcal{Y}).$$
Here $\mathbf{A}_k\mathbf{X}_k$ is the thin quaternion factorization of the $k$-th transformed slice, and $\times_3$ applies a matrix along the time mode. The sum of squared factor norms is the standard factorized stand-in for the slice nuclear norm, which is a convex proxy for rank. The quantity being varied is the transform, not the factorization.
Relation to Prior Work
Two quaternion completion papers motivate the design and fix its endpoints. Low-rank quaternion tensor completion for color video inpainting via a novel factorization strategy defines a quaternion tensor product through a generalized quaternion Fourier transform and completes color video with sequential alternating least squares. Its transform is fixed at the Fourier endpoint, and its multi-mode variant is noted to be computationally heavy. Quaternion Tensor Left Ring Decomposition and Application for Color Image Inpainting shows that quaternion tensor-ring completion beats real-valued tensor completions on color images, but it works purely in the spatial domain with sequential solvers. Our model contains the first paper's setting as the special case $\alpha=\pi/2$. It borrows the second paper's evidence that keeping color as one quaternion value helps.
Three papers supply the machinery for simultaneous updates. Generalized Higher-Order Tensor Decomposition via Parallel ADMM updates all Tucker factors at once with a Jacobi-style ADMM (the alternating direction method of multipliers). Its core shortcut replaces large decompositions with small ones on real tensors. Enhanced Nonconvex Low-Rank Approximation of Tensor Multi-Modes for Tensor Completion factorizes each unfolding into independent factor pairs. Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries shows that row updates depending only on observed entries can run concurrently.
We reuse the "independent factor pair per block" idea. The difference is that our blocks are transform slices, not unfoldings. After splitting off the data-fit constraint with an auxiliary variable, those slices share no variables. This matters because the known weakness of Jacobi updates, oscillation on coupled nonconvex blocks, does not arise between slices: there is nothing coupling them for the updates to fight over. We do not claim a new quaternion core shortcut. Quaternion matrices map to complex adjoint matrices whose singular values repeat those of the quaternion matrix. The real-valued proof likely transfers mechanically, so we do not count it as a contribution.
The fractional side motivates the transform and constrains how the angle is chosen. Quaternion Fractional Fourier Transform: Bridging Signal Processing and Probability Theory establishes Plancherel and convolution theorems for the quaternion fractional transform. The Plancherel result guarantees that $F_\alpha$ preserves energy. Energy preservation matters here because it rules out the trivial way of lowering the slice-norm penalty by shrinking the signal.
Generalized Sampling Theory in the Quaternion Domain: A Fractional Fourier Approach reports that a fixed fractional transform does not suppress non-stationary chirped noise. We take that as a warning: one global angle cannot fit everything, so we test per-segment angles as an extension. Fractional Wavelet-Based Generative Scattering Networks finds that fusing reconstructions from two fractional orders beats a single domain on CelebA, but it chooses the orders by hand. We replace hand choice with held-out selection along a warm-started path.
Research Program
The first piece is the operator. We build a discrete, exactly unitary fractional Fourier matrix for the time mode. It is obtained by taking fractional powers of the DFT's eigenvalues over a Hermite-Gaussian-like eigenbasis, so that $F_\alpha = \exp(-\mu\,\alpha H)$ for a fixed real symmetric generator $H$ and a chosen quaternion imaginary axis $\mu$.
We define the quaternion tensor product in the transformed domain as slice-wise multiplication. This definition decouples slices by construction. We then characterize what it corresponds to in the original domain: a chirp-modulated convolution, following the convolution theorem for the quaternion fractional transform. Because quaternion multiplication does not commute, we must also fix the side of multiplication, and we check that left and right conventions give the same slice ranks when $H$ is real.
The second piece is the solver. It is an ADMM with one auxiliary variable carrying the observed-data constraint. The slice updates for the pairs $(\mathbf{A}_k,\mathbf{X}_k)$ run simultaneously as small quaternion least-squares problems, implemented through the complex adjoint representation on GPU. Moving between the original and transformed domains costs one matrix multiply along time, which is $O(T^2)$ per pixel for $T$ frames. For the clip lengths considered here this is cheap.
The third piece is angle selection. We sweep $\alpha$ over a path from $0$ to $\pi/2$ and beyond, warm-starting each solve from its neighbor. We score each angle by reconstruction error on a random 10% of the observed entries that are hidden from the solver. As an ablation we also take gradient steps on $\alpha$ directly, using $\partial F_\alpha/\partial\alpha = -\mu H F_\alpha$. A local extension assigns separate angles to temporal segments, aimed at the non-stationary failure case the sampling-theory paper describes.
Baselines
The naive reference points are the two endpoints of our own family, run through identical code, rank budget and iteration count. The first is $\alpha=0$ (the identity transform), which amounts to per-frame quaternion low-rank completion. The second is $\alpha=\pi/2$, which reproduces the Fourier-domain quaternion model of Low-rank quaternion tensor completion for color video inpainting via a novel factorization strategy, solved in parallel.
These are the most important comparisons, because they isolate the key ingredient: the interior angle. Beating them means that the selected $\alpha$ gives a statistically reliable PSNR gain over the better endpoint across clips and sampling rates. The better endpoint must itself be chosen on the same held-out entries, so that both sides get the same selection advantage.
The strongest published competitor on hard sampling is LRATM from Enhanced Nonconvex Low-Rank Approximation of Tensor Multi-Modes for Tensor Completion. It reports PSNR 29.464 on the "Suzie" video at 5% sampling, against 23.385 for TMac. We will run the authors' method on our exact masks. Its nonconvex penalty $\gamma$ gets the same held-out tuning budget as our angle. We will also compare against the reported 29.464 where our protocol matches.
For the published quaternion Fourier model (QRTC/MQRTC), no reported result was found on Lacuna for "Stefan" or the VideoSegmentationData clips. We therefore rerun it ourselves with its original sequential solver, and we report both accuracy and wall-clock time.
For color images, the quaternion tensor-ring model of Quaternion Tensor Left Ring Decomposition and Application for Color Image Inpainting reports PSNR 31.310 and SSIM 0.977 on natural color images at 50% sampling. It serves as a secondary reference, with our angle applied along a spatial mode.
For speed, the reference is the Jacobi-versus-sequential gap in Generalized Higher-Order Tensor Decomposition via Parallel ADMM: under 20 seconds versus over 3,000 seconds on fourth-order synthetic tensors, with RSE (relative squared error) about 0.006 versus 0.033 for HOSVD. We will compare our solver in simultaneous and sequential modes on identical hardware.
Why not just…?
Why not just run real-valued parallel ADMM on each color channel separately? This would inherit the proven speed of Generalized Higher-Order Tensor Decomposition via Parallel ADMM, but it discards the correlation between channels. Quaternion Tensor Left Ring Decomposition and Application for Color Image Inpainting reports that the quaternion model beats TMac-TT, TRLRF and TRNNM on color images. That evidence comes from a different transform setting, so we do not assume it transfers. We run our fractional model in two forms: with quaternion slices, and with real slices where color is stacked as an extra mode. If the real version matches, the quaternion part of the proposal is dropped and the fractional-angle claim stands alone.
Why not just use the Fourier transform, which has an FFT and needs no extra parameter? This is the $\alpha=\pi/2$ baseline, and it is the real threat. For largely static or periodic footage like "Suzie" or "News", we expect the selected angle to sit near an endpoint and the gain to be negligible. That outcome would be informative, not embarrassing, because our model contains the Fourier model and cannot lose to it beyond selection noise. The decisive evidence is whether zoom-heavy or fast-panning clips ("Stefan", "Coastguard") pick interior angles with real gains. We also include synthetic quaternion tensors with planted chirps along time, where the right angle is known in advance.
Why not just grid-search $\alpha$ and skip any clever selection? We largely agree, and the proposal is built around exactly this. Held-out grid selection is the main method, and gradient steps on $\alpha$ are only an ablation. Our contribution on the selection side is making the sweep cheap through simultaneous slice updates and warm starts. We report the cost of a full 16-angle path as a multiple of one cold solve. If that multiple is not well below 16, the warm-start claim fails.
Why not just learn a full unitary transform along time from the data? A learned transform is strictly more flexible and could beat any one-parameter family. With 5% of entries observed, though, it has on the order of $T^2$ free parameters to fit from very little data, while our family has one. We run a learned-orthogonal-transform baseline with the same held-out selection. Our bet is that the fractional family wins at low sampling rates and loses at high ones. The crossover point is itself a result worth reporting.
Proposed Experiments
The experiments use the benchmarks the prior papers already report on: "Suzie" and "Hall" from the LRATM study, "Stefan", "News", "Coastguard" and the VideoSegmentationData clips from the quaternion Fourier study, and the natural color image set from the tensor-ring study. We use random-entry masks at sampling rates from 5% to 50%, plus structured masks with missing whole frames and blocks. We report PSNR, SSIM and RSE on the hidden entries and wall-clock time on a single GPU. On the synthetic quaternion chirp tensors, we additionally measure how far the selected angle is from the planted angle.
Three checks decide whether the idea holds. First, on the chirp synthetics, the held-out curve must bottom out at the planted angle. Its effective slice rank must be clearly below both endpoints. If it is not, the premise that fractional rotation lowers rank is wrong.
Second, on real clips, we report the distribution of selected angles and the PSNR gain over the better endpoint. The proposal succeeds only if a meaningful fraction of non-stationary clips select interior angles, with gains exceeding across-mask variability. The per-segment-angle extension is tested on the same clips to see whether it closes any remaining gap.
Third, we run the solver in simultaneous and sequential slice-update modes with identical objectives. The two must reach the same final objective. The simultaneous mode must show the wall-clock reduction that separability predicts, and the full angle path must cost well under the sum of independent solves. If all three checks pass, the result is a completion model that contains the current quaternion Fourier approach as a special case and chooses its own transform from the data at little extra cost.
References
- Low-rank quaternion tensor completion for color video inpainting via a novel factorization strategy
- Quaternion Tensor Left Ring Decomposition and Application for Color Image Inpainting
- Generalized Higher-Order Tensor Decomposition via Parallel ADMM
- Enhanced Nonconvex Low-Rank Approximation of Tensor Multi-Modes for Tensor Completion
- Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries
- Quaternion Fractional Fourier Transform: Bridging Signal Processing and Probability Theory
- Generalized Sampling Theory in the Quaternion Domain: A Fractional Fourier Approach
- Fractional Wavelet-Based Generative Scattering Networks