PaperlayerView exact revision on arXiv

Source-linked AI summary

Binary Phase Retrieval of Cosine Transforms via Local Curvature Minimization

Ronald Ogden, Shwetadwip Chowdhury, Takashi Tanaka, David Fridovich-Keil

arXiv:2610.02112v1eess.IV

TL;DR

Optical phase retrieval for cosine transforms is challenging because sensors capture magnitude rather than phase, and general methods do not use the transform's binary sign structure. The paper develops a curvature-minimizing binary solver and reports consistent reconstructions with MSSSIM of 0.95. The approach does not yet perform well on optically generated transforms.

  • Problem

    Optical sensors capture magnitude but not phase, while general phase-retrieval methods do not exploit the binary sign domain of real-valued cosine transforms.

    Source: §I · pp. 1–2

  • Method

    The algorithm minimizes reconstructed-transform curvature and divides the problem into high-energy blocks solved individually, followed by a lower-dimensional QUBO for inter-block sign discrepancies.

    Source: §I · p. 2, §III · pp. 5–6

  • Results

    The algorithm consistently reconstructs images within an MSSSIM of 0.95.

    Source: §V · p. 9

  • Takeaways & Limitations

    The divide-and-conquer QUBO does not guarantee a globally optimal solution, though the reported retrieval quality leaves little practical room for improvement.

    Source: §III · p. 6

    The algorithm works well on computationally computed transforms but not yet on optically generated transforms, where non-ideal factors can smooth the sharp curvature near zero level sets.

    Source: §V · p. 9

Abstract

from arXiv · show

Cosine transforms see frequent use in image and video compression due to their ease of computation and high energy compaction. This has sparked interest within the optics community in computing cosine transforms optically for compression. When imaging in the Fourier plane to capture a cosine transform, one encounters a phase retrieval problem: optical fields have both magnitude and phase, but cameras only capture the magnitude of the field. Cosine transforms restrict the phase retrieval problem to a binary domain as opposed to the unit circle, but general phase retrieval solutions do not leverage this. In this work, we demonstrate that sign errors in phase retrieval for cosine transforms result in a significant increase in the magnitude of the Hessian of the transform at the error. Motivated by this, we develop an algorithm to solve this binary phase retrieval problem by minimizing the curvature of the reconstructed cosine transform. We demonstrate via computational experiments that given the magnitude of the cosine transform of an image, we can consistently reconstruct the original image within a multiscale structural similarity index of 0.95. We show that the solve time grows approximately linearly with the number of pixels solved.

I. INTRODUCTION

Cosine transforms are useful for compression, but optical measurements capture magnitude without phase, leaving sign recovery as a central challenge. Their real-valued outputs make this a binary problem that general phase-retrieval methods do not exploit.

I. INTRODUCTION

  • Cosine transforms support image and video compression through computational ease and strong energy compaction, motivating optical implementations.Optical sensing, however, captures magnitude rather than phase, which is essential for these applications.Source: §I · p. 1

II. PHASE RETRIEVAL METHODOLOGY

  • Because real-valued images have real-valued cosine transforms, their phase-retrieval problem is binary, but general methods do not exploit this restriction.The paper proposes a binary algorithm that leverages cosine-transform energy compaction and frames its methodology around Hessian-norm minimization and a binary quadratic program.Source: §I · pp. 1–2, §II · p. 2

A. Cosine Transforms of Images

  • A cosine transform is the Fourier transform of the even part of a function, and its intensity can retain spatial-shift information absent from Fourier intensity alone.The cited example contrasts shifted functions; Fourier intensity requires an added tool such as a stationary reference object to recover this information.Source: A. Cosine Transforms of Images · p. 2
  • For nonnegative, integrable, compactly supported even functions, equal cosine-transform magnitudes imply equality almost everywhere.The paper states this uniqueness result as Theorem 1.Source: A. Cosine Transforms of Images · p. 2

B. Motivating Hessian Norm Minimization

The method uses Hessian curvature to distinguish correct from incorrect sign assignments: under stated assumptions, a wrong sign region creates a gradient discontinuity and a singular Hessian contribution.

B. Motivating Hessian Norm Minimization

  • The reconstruction seeks a sign map from {−1, 1} that multiplies the observed magnitude to recover the cosine transform, up to global sign ambiguity.The initial sign is fixed at the origin; without further assumptions, the problem is ill-posed.Source: B. Motivating Hessian Norm Minimization · p. 3
  • The curvature argument assumes a continuous gradient and a gradient bounded away from zero almost everywhere on the transform's zero level set.These conditions make zero level sets unambiguous boundaries between positive and negative regions.Source: B. Motivating Hessian Norm Minimization · p. 3
  • An incorrect sign assignment across a closed curve creates a gradient discontinuity and a Dirac delta in the Hessian, raising its integrated norm as an error indicator.In the one-dimensional example, the incorrect reconstruction has twice the corresponding integral for the correct sign function.Source: B. Motivating Hessian Norm Minimization · p. 3
  • For f(x) = cos(x) on [0, π], the correct sign yields smooth first and second derivatives, unlike the incorrect sign reconstruction.The incorrect reconstruction has a discontinuous first derivative and a Dirac delta in its second derivative.Source: B. Motivating Hessian Norm Minimization · p. 3

C. Discretized Optimization Problem

The continuous curvature objective is translated into a discrete problem by approximating the Hessian with central differences and specifying boundary handling.

C. Discretized Optimization Problem

  • The discrete formulation represents the transform and its magnitude as m × n arrays, with each magnitude entry equal to the absolute value of the corresponding transform entry.The same motivation is intended to hold when spatial sampling is sufficiently high.Source: C. Discretized Optimization Problem · p. 3
  • Central differences approximate the discrete Hessian using the component matrices Hxx, Hxy, and Hyy.The Hessian approximation groups these components in a matrix at each array location.Source: C. Discretized Optimization Problem · pp. 3–4
  • Same padding approximates border Hessians by copying the nearest edge values, and the sign function combines with the magnitude through a Hadamard product.The resulting discrete optimization problem is stated after this boundary convention.Source: C. Discretized Optimization Problem · p. 4

D. Binary Quadratic Program Formulation

The discrete objective is quadratic in the sign variables, allowing its reformulation as a standard quadratic unconstrained binary optimization problem.

D. Binary Quadratic Program Formulation

  • Because every objective term is quadratic in the sign variables, the discrete problem is a binary quadratic program suitable for standard solvers such as Gurobi or Mosek.The formulation is presented in a classical solver-recognizable form.Source: D. Binary Quadratic Program Formulation · p. 4
  • Vectorization and finite-difference matrices, combined through Kronecker products, express the Hessian terms in matrix form.The derivation uses compatible-matrix identities to re-express the discrete objective.Source: D. Binary Quadratic Program Formulation · p. 4
  • Fixing one sign resolves global-sign invariance, and substituting s = 2b − 1 converts the decision variables into binary digits for the final QUBO.The recovered sign array is obtained from the binary solution.Source: D. Binary Quadratic Program Formulation · p. 4

III. OPTIMIZATION ALGORITHM

The algorithm divides cosine-transform phase retrieval into smaller block problems, prioritizes energetic regions, and then corrects sign discrepancies between blocks. This divide-and-conquer approach does not guarantee a globally optimal solution.

III. OPTIMIZATION ALGORITHM

  • The algorithm solves binary phase retrieval blockwise, then uses a lower-dimensional QUBO to resolve sign discrepancies across blocks.This decomposition enables smaller problems to be solved in parallel rather than searching the full image at once.Source: §III · p. 5
  • The mask greedily selects high-energy blocks adjacent to the current connected set, then dilation remedies sparse connectivity.Only the selected fraction of blocks is solved, focusing computation on regions expected to matter most for image reconstruction.Source: §III · p. 5
  • Each selected block is solved with a border of width β, improving sign recovery near its edges at increased solve time.Border pixels are discarded after solving; increasing β improves accuracy but makes solve time grow exponentially with β.Source: §III · pp. 5–6
  • Concatenated block solutions can disagree in sign because each block assumes a positive top-left pixel; a second QUBO estimates blockwise corrections.The corrections are expanded from block signs to pixel signs and combined with the interim solution to form the final phase solution.Source: §III · p. 6
  • The divide-and-conquer method does not guarantee a globally optimal solution, although the authors report little practical room to improve phase-retrieval quality.Source: §III · p. 6

IV. COMPUTATIONAL RESULTS

The computational evaluation applies the solver to DCT magnitudes from the Kodak image suite and reconstructs images through the inverse DCT. Experiments examine sampling, phase-solving coverage, qualitative behavior, and solve time.

IV. COMPUTATIONAL RESULTS

  • The evaluation uses 24 Kodak Lossless True Color images, each 768 × 512 or 512 × 768, and reconstructs each image from its DCT magnitude.The recovered signs are applied to the magnitude before the inverse DCT produces the reconstructed image.Source: §IV · pp. 6–7
  • Zero-padding the original image creates an arbitrarily small DCT sampling interval, while dimensions are adjusted to divide evenly into solver blocks.Source: §IV · p. 7
  • The experiments assess phase-retrieval success across sampling frequencies, reconstructed-image distortion as more pixels are solved, qualitative masking benefits, and solve-time scaling.The planned measurements vary the sampling frequency and the fraction of pixels whose phase is solved.Source: §IV · p. 7

A. Phase Retrieval Success vs Sampling Interval

With greater padding, phase retrieval yields higher and less variable neighbor-similarity scores across images. The section also relates correctness-map continuity and reconstruction quality to the phase-recovery process.

A. Phase Retrieval Success vs Sampling Interval

  • Neighbor similarity score averages the fraction of neighboring correctness signs that match, excluding neighborhoods touching unsolved pixels.Low-quality solutions tend toward 0.5, while improved phase retrieval moves the score toward 1.Source: A. Phase Retrieval Success vs Sampling… · p. 7
  • As padding increases, neighbor similarity scores rise and show less variance across images, indicating stronger and more consistent phase retrieval.The experiment uses α = 0.1, β = 1, and 6 × 6 blocks; upsampling helps the optimization detect discontinuities in the reconstructed transform's derivative.Source: A. Phase Retrieval Success vs Sampling… · p. 7
  • Figure 6 presents ˆF0 image reconstructions for two images from the Section IV-B experiment at α = 0.01 and α = 0.1, alongside phase-correctness arrays described in Section IV-A.In the phase-correctness images, white represents 1, gray 0, and black -1.Source: Figure 6 · p. 8
  • Reconstruction distortion decreases as the fraction of pixels with solved phase increases, and reasonable quality is possible when only a fraction is solved.Source: Figure 7 · p. 8

B. Pixels Solved vs Reconstruction Distortion

Reconstruction quality improves as more transform pixels are solved for, with MSSSIM exceeding 0.95 across almost the entire dataset. Solving a smaller fraction can produce blur or ringing by omitting high-frequency information.

B. Pixels Solved vs Reconstruction Distortion

  • MSSSIM exceeded 0.95 across almost the entire dataset as the proportion of pixels solved for increased.The experiment varied α from 0.1 to 1.0 in increments of 0.1.Source: B. Pixels Solved vs Reconstruction… · p. 8
  • The distortion experiment used m_p = n_p = 3000, β = 1, and m′ = n′ = 6 while varying α from 0.1 to 1.0.The bit recovery ratio is the number of pixels whose phase was solved divided by the number of cosine-transform array elements.Source: B. Pixels Solved vs Reconstruction… · p. 8
  • Low α can cause blur or ringing because masking low-energy regions loses high-frequency information.The house image’s phase-correctness plot highlights directional frequency bands with higher energy relative to the rest of the transform.Source: B. Pixels Solved vs Reconstruction… · p. 8

C. Solution Time

In the tested range, total solve time grows approximately linearly with the number of bits solved. Parallel block solving dominates the superlinear time for resolving inter-block discrepancies.

C. Solution Time

  • Total solve time grew approximately linearly with the number of bits solved over the tested α range.Inter-block discrepancy resolution remained significantly faster than parallel block solving in this range.Source: C. Solution Time · p. 8
  • Parallel block-solving time grew linearly with bits solved because individual block size was constant.The experiment used 12 workers.Source: C. Solution Time · p. 8
  • Inter-block discrepancy resolution time grew superlinearly because its feasible space grows exponentially with the number of bits solved.Despite this growth, its measured time was always significantly less than the individual block solution time over the tested α range.Source: C. Solution Time · p. 8

V. CONCLUSION

The algorithm retrieves phase by minimizing reconstructed-transform curvature and leverages the energy compaction and restricted phase domain of cosine transforms. It consistently reconstructs images to within an MSSSIM of 0.95, but optical inputs and global optimality remain limitations.

V. CONCLUSION

  • The algorithm retrieves cosine-transform phase by minimizing the curvature of the reconstructed transform and leveraging cosine transforms’ energy compaction and restricted phase domain.The table passage identifies the hardware and software environment, but supplies no values to report.Source: §V · pp. 8–9, Table I · p. 9
  • The phase-solution time plot indicates that total solution time grows linearly with bit recovery ratio in its reported regime.The parallel solution of individual blocks drives total solution time in that regime.Source: Figure 8 · p. 9
  • The algorithm consistently reconstructed images to within an MSSSIM of 0.95.The conclusion reports this outcome for the demonstrated algorithm.Source: §V · p. 9
  • The algorithm works well on computationally computed cosine transforms but does not yet perform well on optically generated transforms.Misalignment, ambient light, vibration, and other lab factors can smooth the sharp curvature along an ideal transform’s zero level set.Source: §V · p. 9
  • The block-decomposed algorithm is not guaranteed to converge to a global optimum; ADMM could guarantee optimality but may take longer.The blocks are solved independently before inter-block sign discrepancies are resolved.Source: §V · p. 9

APPENDIX A PROOF OF THEOREM 1

The appendix proves uniqueness under the stated assumptions by using analyticity and nonnegativity to resolve the sign ambiguity. It also derives an identity by replicating matrix rows and columns and applying vectorization.

APPENDIX A PROOF OF THEOREM 1

  • Compact support makes the cosine transforms entire functions, so their restrictions to R2 are real analytic.The proof defines F := Fc{f} and G := Fc{g}.Source: Appendix A · p. 9
  • Analyticity and equality of squared transforms imply F ≡ G or F ≡ −G; nonnegativity makes both transforms positive at zero, selecting F ≡ G and yielding equality by cosine-transform uniqueness.The theorem assumes even, nonnegative, integrable functions with compact support.Source: Appendix A · p. 9

APPENDIX B DERIVATION OF (39)

  • Multiplication by Kronecker products replicates matrix columns and rows; applying vec(·) and identity (25) gives the desired identity.The construction concatenates n′ copies of each column and m′ copies of each row.Source: Appendix B · p. 9

APPENDIX C NOTE ON ASSUMPTION 2

Convolution-based counterexamples to Assumption 2 can produce degenerate continuous curves, but such cases are topologically rare: DΩ is nowhere dense and its complement is dense.

APPENDIX C NOTE ON ASSUMPTION 2

  • Convolving two images can give a counterexample to Assumption 2, with degenerate continuous curves where the transform and its gradient both vanish.The appendix argues such counterexamples are topologically rare.Source: Appendix C · pp. 9–10
  • DΩ is nowhere dense in I, while I \ DΩ is dense, so images with simultaneous transform and gradient zeros are topologically rare.DΩ contains images whose transform and gradient vanish together somewhere in the compact domain Ω.Source: Appendix C · p. 10
  • The proof perturbs an arbitrary image using three parameters; its Dirac-delta construction is for exposition, with a similar construction in I available.The perturbation is parameterized by c in R^3, and the replacement function can be chosen with sufficiently small support.Source: Appendix C · p. 10
  • A nonsingular parameter-gradient matrix makes J a submersion; almost all parameters yield transversality, and codimension 3 exceeds the domain dimension 2.Transversality therefore forces the perturbed 1-jet to avoid the origin, while the perturbation can be arbitrarily small in L1.Source: Appendix C · p. 10
  • Continuity and compactness give a positive margin for images outside DΩ; sufficiently small L1 perturbations preserve the absence of simultaneous zeros.This makes I \ DΩ open, completing the nowhere-dense result.Source: Appendix C · p. 10
Loading 2610.02112v1…