Completeness, stability, and wavelet-class characterization for the stabilized dyadic zero-crossing representation (Mallat, 1991)

Mallat's 1991 paper introduced a stabilized multiscale zero-crossing representation: at each dyadic scale of a wavelet transform whose wavelet is the second derivative of a smoothing function, one records the positions of the transform's zero-crossings together with the integral of the transform between consecutive zero-crossings, yielding a piecewise-constant $L^2$ descriptor with a natural distance. The paper proved convergence of an alternating-projection reconstruction toward some element consistent with the descriptor, and observed empirically that the recovered signal is independent of the initialization, but did not prove uniqueness, completeness, or stability. The open problem is to determine for which signal classes and which dyadic wavelets this representation is complete and stable — i.e., whether the feasibility set of consistent wavelet transforms is a singleton, whether signal perturbations are controlled by descriptor perturbations, and which wavelets (beyond the frame/partition-of-unity condition) admit these guarantees. Berman and Baras (1993) showed such representations are in general nonunique, so the surviving question is a sharp characterization problem.

Background

Zero-crossings of smoothed signals have been used to locate sharp variations since Marr and Hildreth's edge-detection theory: convolving a signal with a Gaussian and marking the zero-crossings of the second derivative of the result locates the inflection points of the smoothed signal, which track edges as the smoothing scale varies. Logan's theorem showed that a one-octave bandpass signal is determined, up to a multiplicative constant, by its zero-crossings alone, but this recovery is numerically fragile, and for general signals the zero-crossings of a single filtered version are far from determining. In the scale-space literature, Yuille and Poggio proved scaling theorems for zero-crossings of Laplacian-of-Gaussian-filtered signals (the Gaussian is the only filter that creates no generic new zero-crossings as scale increases), and Hummel and Moniot showed that reconstruction from zero-crossings in dense-scale Gaussian scale space is possible in principle but unstable. A recurring obstacle is that zero-crossing locations alone admit no satisfactory metric, so the instability of the descriptor is hard even to formalize.

Mallat's 1991 paper recast this question in wavelet language and introduced the object of this problem. A dyadic wavelet is an $L^2$ function $\psi$ whose Fourier transform satisfies the partition-of-unity (frame) condition $\sum_{j=-\infty}^{\infty}|\hat{\psi}(2^j\omega)|^2=1$; the dyadic wavelet transform of $f\in L^2(\mathbb{R})$ is the sequence $(W_{2^j}f)_{j\in\mathbb{Z}}$ with $W_{2^j}f=f*\psi_{2^j}$ and $\psi_s(x)=s^{-1}\psi(x/s)$. The partition of unity makes this redundant transform invertible: $\|f\|^2=\sum_j\|W_{2^j}f\|^2$ and $f=\sum_j W_{2^j}f*\tilde\psi_{2^j}$, so the transform itself is complete. When $\psi=\frac{d^2\theta}{dx^2}$ for a smoothing function $\theta$, one has $W_{2^j}f=2^{2j}\frac{d^2}{dx^2}(f*\theta_{2^j})$, so the zero-crossings of $W_{2^j}f$ are exactly the inflection points of $f*\theta_{2^j}$: multiscale Marr–Hildreth edges computed on the sparse dyadic scale sequence rather than a dense one, at a fraction of the computation.

To stabilize the descriptor, Mallat augmented the zero-crossing positions: at each scale, if $(z_n)_n$ are the consecutive zero-crossings of $W_{2^j}f$, record the integrals $e_n=\int_{z_{n-1}}^{z_n}W_{2^j}f(x)\,dx$, and encode the pair as a piecewise-constant function $Z_{2^j}f$ equal to $e_n/(z_n-z_{n-1})$ on each inter-zero-crossing interval. Then $(Z_{2^j}f)_j\in l^2(L^2)$, the Hilbert space of sequences $(g_j)$ with $g_j\in L^2$ and $\sum_j\|g_j\|^2<\infty$, and $\sum_j\|Z_{2^j}f\|^2\le\|f\|^2$; the descriptor therefore carries a natural global and locally windowsable distance $d(Zf,Zg)^2=\sum_j\|Z_{2^j}f-Z_{2^j}g\|^2$, used in the paper's coarse-to-fine stereo matching application. Note that the available distance bounds are one-sided: only $d(Zf,Zg)^2\le\|f\|^2+\|g\|^2$ is known, which says nothing about how much a signal can change under a small descriptor change.

Reconstruction was formulated as a convex feasibility problem in $l^2(L^2)$. Let $V$ be the closed subspace of sequences that are dyadic wavelet transforms of some signal (the range of the transform), and let $\Gamma$ be the set of sequences having, at every scale, the same zero-crossing locations and the same inter-zero-crossing integrals as $Wf$ (zero-crossings defined through strict positivity/negativity of integrals on adjacent intervals). One seeks an element of $\Gamma\cap V$ by alternating projections, the classical projections-onto-convex-sets method of Youla and Webb: the projection onto $\Gamma$ is a per-interval constrained least-squares step with a closed-form thresholding solution, and the projection onto $V$ uses the frame reconstruction formula. The iterates converge weakly to an element of $\Gamma\cap V$, with $O(N\log^2 N)$ cost per iteration in the discrete implementation. Empirically, on Diracs, step edges, sinusoids, Brownian processes, and image scan-lines, the reconstructed signal was independent of the initial sequence, suggesting that $\Gamma\cap V$ is a singleton containing the original transform; but this uniqueness, and the completeness and stability of the stabilized representation, were left unproven, as was the question of which dyadic wavelets admit these properties. A companion line of work (Mallat and Zhong, 1992) developed the parallel representation by wavelet transform modulus maxima with the same open question. Subsequent work studied the same feature representations: Berman and Baras analyzed uniqueness and stability of the maxima and zero-crossings representations, Zou, Tewfik, and Xu gave completeness conditions for partial dyadic wavelet domain representations of finite discrete signals, and Cvetković and Vetterli developed convex-representation and filter-bank design theory for consistent reconstruction from extrema and zero-crossings — none of which settled the original question.

Problem Statement

For the stabilized dyadic zero-crossing representation of Mallat (1991) — at every dyadic scale $2^j$ of the dyadic wavelet transform $W_{2^j}f=f*\psi_{2^j}$ with $\psi$ satisfying $\sum_{j}|\hat{\psi}(2^j\omega)|^2=1$ and $\psi=\theta''$, the zero-crossing positions of $W_{2^j}f$ together with the integrals $\int_{z_{n-1}}^{z_n}W_{2^j}f(x)\,dx$ between consecutive zero-crossings (plus the coarse-scale residual $S_{2^J}f$ in finite-scale versions) — settle the following three interlinked questions, all of which are required for a complete answer and which the source paper raised on numerical evidence but did not prove.

1. Completeness and uniqueness. For which classes of signals $f\in L^2$ does this descriptor determine $f$? Equivalently, when is the feasibility set $\Gamma\cap V$ (sequences sharing the given zero-crossings and integrals, intersected with the closed subspace of valid dyadic wavelet transforms) a singleton, so that the alternating-projection reconstruction $P_\Gamma\circ P_V$ returns the original dyadic wavelet transform of $f$ for every initialization, as observed empirically for Diracs, step edges, sinusoids, Brownian processes, and image scan-lines? Since Berman and Baras (1993) showed these feature representations are in general nonunique, a complete answer is expected to be a sharp characterization — signal classes and degeneracy conditions — of when uniqueness holds and how it fails.

2. Stability. Establish, or rule out by counterexample, quantitative stability: a Lipschitz-type bound of the form $\|f-g\|\le C\,d(Zf,Zg)$ (globally and in the localized version around a point) between the $L^2$ distance of two signals and the distance between their stabilized zero-crossing descriptors, including perturbations of the descriptor that create, annihilate, or merge zero-crossing pairs; only the one-sided descriptor bound $d(Zf,Zg)^2\le\|f\|^2+\|g\|^2$ and partial stability results (bounded-input/bounded-output, and Lipschitz under restricted perturbations) are currently known.

3. Wavelet class. Characterize the class of dyadic wavelets for which the completeness and stability above hold, relative to the partition-of-unity (frame) condition and the requirement that $\psi$ be the second derivative of a smoothing function, and relate this characterization to the perfect-reconstruction filter-bank conditions known to enable consistent reconstruction.

References

1. S. Mallat (1991). Zero-crossings of a wavelet transform. IEEE Transactions on Information Theory 37(4):1019–1033. DOI 10.1109/18.86995. https://doi.org/10.1109/18.86995
2. Z. Berman and J. S. Baras (1993). Properties of the multiscale maxima and zero-crossings representations. IEEE Transactions on Signal Processing 41(12):3216–3231. DOI 10.1109/78.258069. https://doi.org/10.1109/78.258069
3. H. Zou, A. H. Tewfik, and W. Xu (1993). Completeness and stability of partial dyadic wavelet domain signal representations. IEEE ICASSP 1993, vol. 3, pp. 312–315. DOI 10.1109/ICASSP.1993.319498. https://doi.org/10.1109/ICASSP.1993.319498
4. Z. Cvetković and M. Vetterli (1995). Discrete-time wavelet extrema representation: design and consistent reconstruction. IEEE Transactions on Signal Processing 43(3):681–693. DOI 10.1109/78.370622. https://doi.org/10.1109/78.370622
5. A. E. Çetin and R. Ansari (1994). Signal recovery from wavelet transform maxima. IEEE Transactions on Signal Processing 42(1):194–196. DOI 10.1109/78.258135. https://doi.org/10.1109/78.258135
6. S. Mallat and S. Zhong (1992). Characterization of signals from multiscale edges. IEEE Transactions on Pattern Analysis and Machine Intelligence 14(7):710–732. DOI 10.1109/34.142909. https://doi.org/10.1109/34.142909
7. R. Hummel and R. Moniot (1989). Reconstructions from zero crossings in scale space. IEEE Transactions on Acoustics, Speech, and Signal Processing 37(12):2111–2130. DOI 10.1109/29.45555. https://doi.org/10.1109/29.45555
8. A. L. Yuille and T. A. Poggio (1986). Scaling theorems for zero crossings. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8(1):15–25. DOI 10.1109/TPAMI.1986.4767748. https://doi.org/10.1109/TPAMI.1986.4767748
9. B. F. Logan (1977). Information in the zero crossings of bandpass signals. Bell System Technical Journal 56(4):487–510. DOI 10.1002/j.1538-7305.1977.tb00522.x. https://doi.org/10.1002/j.1538-7305.1977.tb00522.x
10. D. Marr and E. Hildreth (1980). Theory of edge detection. Proceedings of the Royal Society of London B 207(1167):187–217. DOI 10.1098/rspb.1980.0020. https://doi.org/10.1098/rspb.1980.0020
11. D. C. Youla and H. Webb (1982). Image restoration by the method of convex projections: Part 1—Theory. IEEE Transactions on Medical Imaging 1(2):81–94. DOI 10.1109/TMI.1982.4307555. https://doi.org/10.1109/TMI.1982.4307555
12. S. Watanabe, Y. Akimoto, T. Komatsu, and T. Saito (1995). A new stabilized zero-crossing representation in the wavelet transform domain and signal reconstruction. IEEE ICIP 1995, vol. 1, pp. 37–40. DOI 10.1109/ICIP.1995.529033. https://doi.org/10.1109/ICIP.1995.529033
13. S. Meignen and P.-Y. Guméry (2007). Reconstruction of finite signal derivatives from multiscale extrema representations: application to transient estimation and signal approximation. IEEE Transactions on Signal Processing 55(4):1554–1559. DOI 10.1109/TSP.2006.887570. https://doi.org/10.1109/TSP.2006.887570
14. D. Ravi and Y. V. Venkatesh (2000). A new framework for reconstruction of images from boundaries. SIAM Journal on Applied Mathematics 60(6):1841–1866. DOI 10.1137/S0036139998343861. https://doi.org/10.1137/S0036139998343861
15. P. Boufounos and R. G. Baraniuk (2008). Reconstructing sparse signals from their zero crossings. IEEE ICASSP 2008, pp. 3361–3364. DOI 10.1109/ICASSP.2008.4518371. https://doi.org/10.1109/ICASSP.2008.4518371
16. B. G. Bodmann and C. Liner (2011). Stable signal recovery from the roots of the short-time Fourier transform. SPIE Optical Engineering and Applications, Wavelets and Sparsity XIV, vol. 8138, article 813817. DOI 10.1117/12.894941. https://doi.org/10.1117/12.894941
17. H.-Y. Lai, P. Martínez-Nuevo, and A. V. Oppenheim (2017). An iterative reconstruction algorithm for amplitude sampling. IEEE ICASSP 2017, pp. 4576–4580. DOI 10.1109/ICASSP.2017.7953023. https://doi.org/10.1109/ICASSP.2017.7953023
18. C. Wijenayake, A. Ignjatović, and G. Keller (2019). On reconstruction of bandlimited signals from purely timing information. Signal Processing 159:89–92. DOI 10.1016/J.SIGPRO.2019.02.002. https://doi.org/10.1016/J.SIGPRO.2019.02.002
19. D. Van De Ville and M. Unser (2009). Wavelet primal sketch representation using Marr wavelet pyramid and its reconstruction. SPIE Optical Engineering and Applications, Wavelets XIII, vol. 7446, article 74460W. DOI 10.1117/12.825972. https://doi.org/10.1117/12.825972