My open problems – Yann Traonmilin

Status: a question described as open in a paper is not necessarily still open today. I haven’t checked everything.

Abbreviations: RIP = restricted isometry property; GPGD = generalized projected gradient descent; RED = regularization by denoising; SOR = stochastic orthogonal regularization; DPS = diffusion posterior sampling. PDF page numbers refer to the versions reviewed, including any cover sheets.

Regularizer design

Open question. Is the sufficient RIP threshold pointwise equal to the strongly sharp threshold for every model and regularizer?
Source: Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all. §7, PDF pp.46–47.
Open question. For each fixed ambient dimension and sparsity, does the strongly sharp sparse-recovery threshold equal the weak family-wide threshold?
Source: Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all. §7, PDF p.47.
Open question. Is the proposed block-structured RIP threshold weakly sharp?
Source: Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all. §7, PDF p.47.
Open question. For a prescribed regularizer class, when is the best admissible RIP threshold positive?
Source: Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all. §7, PDF p.47.
Open question. Is the optimal regularizer attained, how can it be characterized, and is it unique? This is partially answered in A theory of optimal convex regularization for low-dimensional recovery
Source: Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all. §7, PDF p.47.
Research direction. Can optimal-regularizer theory extend to Banach spaces and off-grid models?
Source: A theory of optimal convex regularization for low-dimensional recovery. §2.3, PDF p.9.
Open question. Do descent-cone-volume and fixed-dimensional random-kernel criteria select the same optimal regularizers? This depends on the family of regularizers, still open for “almost all” convex regularizers
Source: A theory of optimal convex regularization for low-dimensional recovery. §2.3, PDF p.9.
Open question. Can the sharp RIP threshold be computed explicitly for arbitrary regularizers, even for sparse or low-rank recovery?
Source: A theory of optimal convex regularization for low-dimensional recovery. §3.1, PDF p.13.
Open question. Does the necessary threshold equal the sharp threshold, in special cases or generally?
Source: A theory of optimal convex regularization for low-dimensional recovery. §3.1, PDF pp.15–16.
Research direction. Can nuclear-norm optimality be extended from symmetric to nonsymmetric matrices?
Source: A theory of optimal convex regularization for low-dimensional recovery. §3.2, PDF p.17.
Open question. Is ℓ₁ uniquely optimal for each fixed sparsity greater than one?
Source: A theory of optimal convex regularization for low-dimensional recovery. §3.2, PDF p.19.
Open question. For sparsity in levels and sparse-plus-low-rank models, what is optimal beyond weighted atomic-norm families?
Source: A theory of optimal convex regularization for low-dimensional recovery. §4, PDF p.25.
Open question. Which properties of a compliance measure guarantee an optimal convex regularizer exists?
Source: A theory of optimal convex regularization for low-dimensional recovery. §5, PDF p.25.
Research direction. How do compliance measures transform under model intersections, unions, and sums?
Source: A theory of optimal convex regularization for low-dimensional recovery. §5, PDF p.25.
Research direction. How should regularizers trade exact identifiability against noise stability, possibly with measurement design?
Source: A theory of optimal convex regularization for low-dimensional recovery. §5, PDF p.25.
Open question. Can optimal regularizers be constructed by optimizing the compliance quantities without guessing the answer?
Source: A theory of optimal convex regularization for low-dimensional recovery. §5, PDF pp.25–26.
Research direction. What regularizers are optimal under statistical-dimension or Gaussian-width criteria for nonuniform recovery?
Source: A theory of optimal convex regularization for low-dimensional recovery. §5, PDF p.26.

Hilbert-space recovery

Research direction. Can the sufficient RIP threshold extend to non-Hilbert measurement norms and structured acquisitions such as rank-one projections?
Source: Compressed sensing in Hilbert spaces. §5.3, PDF p.23.
Open question. What weaker necessary-and-sufficient geometric condition characterizes stable finite-dimensional embeddings?
Source: Compressed sensing in Hilbert spaces. §5.4, PDF pp.23–24.
Open question. Can a sufficient regularizer-dependent RIP constant be established for kernel-Hilbert formulations of super-resolution?
Source: Compressed sensing in Hilbert spaces. §5.5, PDF p.24.
Open question. Which usual Banach-space models have finite-dimensional normalized secant sets in suitable kernel metrics? This is partially answered in Compressive Statistical Learning with Random Feature Moments
Source: Compressed sensing in Hilbert spaces. §5.5, PDF p.24.

Optimal algorithms and RED

Open question. Is orthogonal projection near-optimal for arbitrary unions of subspaces, and what projections are optimal for general models?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §3.3, PDF pp.31–32.
Research direction. Do the sparse-projection near-optimality results extend to low-rank recovery and singular-value thresholding?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §3.3, PDF p.31.
Open question. What algorithmic optimality criteria capture structured-noise stability as well as identifiability? some insights in From sparse recovery to plug-and-play priors, understanding trade-offs for stable recovery with generalized projected gradient descent.
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §3.3, PDF p.32.
Research direction. Can the analysis cover other data-fit directions, including ℓ₁ regression, and implicit algorithms? some insights in From sparse recovery to plug-and-play priors, understanding trade-offs for stable recovery with generalized projected gradient descent.
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §4.1, PDF p.33.
Open question. Within meaningful larger classes of averaged-direction methods, is GPGD optimal or can linear convergence be faster?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §§4.2–4.3, PDF pp.34–35.
Research direction. Can approximate-projection analysis explain the observed difference between GM-RED and plug-and-play methods?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. §5.2.3, PDF p.40.
Research direction. How does optimality change if uniform linear convergence is required only after a finite burn-in?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. Conclusion, PDF pp.46–47.
Open question. How can denoisers be trained with controlled restricted Lipschitz constants?
Source: Towards optimal algorithms for the recovery of low-dimensional models with linear rates. Conclusion, PDF p.47.
Open question. Can modified RED achieve stable recovery under generic restricted-Lipschitz projections without closeness to orthogonal projection?
Source: A note on the convergence of RED algorithms under minimal hypotheses and open questions. End of §3, PDF p.4.
Open question. Can classical RED converge under restricted-isometry and restricted-Lipschitz assumptions with useful constants?
Source: A note on the convergence of RED algorithms under minimal hypotheses and open questions. §4, PDF p.5.
Open question. Under what recovery assumptions is classical or modified RED preferable to GPGD?
Source: A note on the convergence of RED algorithms under minimal hypotheses and open questions. §4, PDF p.5.
Research direction. Can the backprojection be estimated automatically for different structured noises, with corresponding guarantees?
Source: From sparse recovery to plug-and-play priors, understanding trade-offs for stable recovery with generalized projected gradient descent. Conclusion, PDF p.9.
Research direction. How should idempotence regularization be combined with SOR and other projection-training constraints?
Source: From sparse recovery to plug-and-play priors, understanding trade-offs for stable recovery with generalized projected gradient descent. Conclusion, PDF p.9.

Diffusion and learned priors

Research direction. Can diffusion-prior recovery theory cover distributions supported on nonlinear manifolds?
Source: A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm. §6, PDF p.10.
Research direction. Can the framework yield sample-complexity guarantees for DPS and diffusion-based posterior sampling or plug-and-play methods?
Source: A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm. §6, PDF p.10.
Research direction. Can diffusion-prior guarantees extend to nonlinear forward operators, such as phase retrieval?
Source: A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm. §6, PDF p.10.
Research direction. Can recovery be made provably robust to measurement noise and learned-prior mismatch?
Source: A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm. §6, PDF p.10.
Open question. Can training control Φ_P, or can SOR itself be proved to control it?
Source: Stochastic Orthogonal Regularization for deep projective priors. §2.2, PDF p.7.
Open question. What is the optimal sampling distribution for stochastic orthogonal regularization?
Source: Stochastic Orthogonal Regularization for deep projective priors. §2.3, PDF p.7.
Research direction. Can SOR be adapted to other norms and reconstruction metrics?
Source: Stochastic Orthogonal Regularization for deep projective priors. Discussion, PDF p.15.
Research direction. How can SOR be extended to variational autoencoders, diffusion models, and nondeterministic priors?
Source: Stochastic Orthogonal Regularization for deep projective priors. Conclusion, PDF p.16.
Research direction. How should approximate, rather than exact, membership in an atomic model be quantified?
Source: Disentangled latent representations of images with atomic autoencoders. §II, PDF p.3.
Open question. Can atomic disentanglement be proved, using a rigorous notion of irreducible atom-generating functions?
Source: Disentangled latent representations of images with atomic autoencoders; Max-sparsity atomic autoencoders with application to inverse problems. Conclusions, PDF pp.5 and 12 respectively.
Research direction. Can atomic autoencoders yield higher-level semantic disentanglement?
Source: Disentangled latent representations of images with atomic autoencoders. Conclusion, PDF p.5.
Research direction. Can normalizing latent blocks improve navigation through the learned representation?
Source: Disentangled latent representations of images with atomic autoencoders. Conclusion, PDF p.5.
Research direction. Can learned atomic representations be given bounded-distortion guarantees?
Source: Disentangled latent representations of images with atomic autoencoders. Conclusion, PDF p.5.
Research direction. Can max-sparsity atomic autoencoders be extended to photorealistic, textured images?
Source: Max-sparsity atomic autoencoders with application to inverse problems. Conclusion, PDF p.12.
Research direction. Can post-training quantization bounds extend to Vision Transformers, including normalization and multi-head attention?
Source: On the impact of the parametrization of deep convolutional neural networks on post-training quantization. §6, PDF p.10.

Off-grid spikes and nonconvex recovery

Research direction. How should basin theory handle overestimated spike counts and non-isolated sets of minimizers?
Source: The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem. Remark 2.2, PDF p.12.
Open question. Can full convergence and measurement guarantees avoid the exponential-in-dimension grid cost of initialization?
Source: Projected gradient descent for non-convex sparse spike estimation; An algorithm for non-convex off-the-grid sparse spike estimation with a minimum separation constraint. Conclusions, PDF pp.4 and 3 respectively.
Research direction. Can alternative pruning, dimension reduction, or quasi-Newton acceleration improve sparse-spike reconstruction?
Source: Projected gradient descent for non-convex sparse spike estimation. Conclusion, PDF p.4.
Research direction. What stability guarantees hold for practical spike-recovery algorithms under noise and model mismatch?
Source: Projected gradient descent for non-convex sparse spike estimation; An algorithm for non-convex off-the-grid sparse spike estimation with a minimum separation constraint; Estimation of off-the-grid sparse spikes with over-parametrized projected gradient descent: theory and application. Conclusions, PDF pp.4, 3, and 30 respectively.
Open question. Can restrictive RIP and measurement-complexity requirements be reduced toward finite-dimensional sparse-recovery scales?
Source: Estimation of off-the-grid sparse spikes with over-parametrized projected gradient descent: theory and application. §3, PDF p.14; conclusion, p.30.
Research direction. Can over-parameterized recovery theory extend beyond Gaussian kernels?
Source: Estimation of off-the-grid sparse spikes with over-parametrized projected gradient descent: theory and application. Conclusion, PDF p.30.
Research direction. Can the required projection distance be estimated in practice instead of supplied as an oracle quantity?
Source: Estimation of off-the-grid sparse spikes with over-parametrized projected gradient descent: theory and application. Conclusion, PDF p.30.
Conjecture. Can the ambient-dimension dependence of the basin bound be removed for Gaussian measurements with high probability?
Source: On strong basins of attractions for non-convex sparse spike estimation: upper and lower bounds. PDF p.6.
Research direction. Can nonasymptotic upper and lower basin bounds match the basins observed experimentally?
Source: On strong basins of attractions for non-convex sparse spike estimation: upper and lower bounds. §6, PDF pp.11–12.
Research direction. Can direct Hessian analysis handle several spikes and structured measurement operators where RIP is poorly suited?
Source: On strong basins of attractions for non-convex sparse spike estimation: upper and lower bounds. §6, PDF pp.11–12.
Research direction. Can efficient initializations give quantitative end-to-end guarantees for super-resolution and Gaussian-mixture recovery?
Source: The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension. §4, PDF p.18; §5, p.19.
Research direction. Can basin theory be applied to low-rank tensor recovery?
Source: The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension. §5, PDF p.19.
Research direction. Can basin theory and suitable RIP guarantees be established for learned neural generative models?
Source: The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension. §5, PDF p.19.
Research direction. Can nonuniform recovery analysis substantially improve the quantitative basin bounds?
Source: The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension. §5, PDF p.19.
Research direction. Which alternative greedy block-selection rules improve projected block-coordinate descent?
Source: Projected Block Coordinate Descent for sparse spike estimation.. §IV, PDF p.5.
Research direction. Can projected block-coordinate updates be parallelized effectively?
Source: Projected Block Coordinate Descent for sparse spike estimation.. §IV, PDF p.5.
Research direction. Can sketched reconstruction operate on full 3D data rather than separate 2D slices?
Source: Sketched over-parametrized projected gradient descent for sparse spike estimation. Conclusion, PDF p.5.
Open question. Why does sketching sometimes slightly improve reconstruction accuracy?
Source: Sketched over-parametrized projected gradient descent for sparse spike estimation. Conclusion, PDF p.5.

Compressive statistical learning

Open question. Can practical compressive-learning optimization algorithms be proved efficient and accurate?
Source: Compressive Statistical Learning with Random Feature Moments; Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. PDF p.12; §7, PDF p.29 respectively.
Open question. Can model-bias bounds and oracle inequalities be sharpened and extended to other losses?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.24.
Open question. Can compressive statistical learning achieve fast excess-risk rates under suitable assumptions?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.24.
Research direction. Can sketching theory explain statistical-information preservation through neural-network layers and pooling?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.24.
Research direction. What trade-offs connect differential privacy and learning accuracy from perturbed or masked sketches?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.24.
Research direction. How should task-compatible kernels and sketches be designed for kernel PCA, clustering, classification, and regression?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF pp.24–25.
Open question. How universal is a fixed kernel: which learning tasks can share one database sketch?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.25.
Research direction. Can sketches based on U-statistics support ranking and tasks involving pairs or tuples of samples?
Source: Compressive Statistical Learning with Random Feature Moments. Conclusion, PDF p.25.
Open question. Can sufficient sketch sizes approach O(kd), rather than O(k²d), and match empirical phase transitions?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling; Compressive learning for patch-based image denoising. §3.4, PDF p.11 and §7, p.29; §6, PDF pp.18–19 respectively.
Open question. What lower bounds show whether sketch-size and mixture-separation assumptions are necessary?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §7, PDF p.29.
Research direction. Can structural centroid constraints yield sharper bias control and faster compressive clustering?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §3, PDF p.8.
Open question. Can overmodeling with an increasing number of Dirac components yield statistical consistency?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §3, PDF p.9.
Research direction. Can higher-dimensional convex or lifted approaches give provable Fourier-sketch decoders without prohibitive computation?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §3.3, PDF p.11; §7, p.29.
Open question. Can Gaussian-mixture bias terms, including the generalized KL contribution, be controlled as sharply as in clustering?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §4, PDF p.13.
Research direction. Can guarantees be proved for fast structured approximations to Gaussian sketching matrices by analyzing their kernels?
Source: Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling. §7, PDF p.29.

Compressive image models

Research direction. Can low-rank covariance parameters be recovered with Frobenius-error guarantees from sketches?
Source: Compressive learning for patch-based image denoising. §5.2, PDF p.13.
Open question. What separation notion and RIP theory fit zero-mean mixtures with differently oriented covariance subspaces?
Source: Sketched learning for image denoising; Compressive learning for patch-based image denoising. §3.1, PDF p.6; §7, PDF p.22 respectively.
Research direction. Can Fourier-frequency distributions be adapted specifically to zero-mean Gaussian mixtures?
Source: Sketched learning for image denoising. Conclusion, PDF p.10.
Research direction. Can LR-COMP be accelerated using sparse-spike recovery algorithms with guarantees?
Source: Sketched learning for image denoising. Conclusion, PDF p.10.
Research direction. Can sketch scale and covariance ranks be selected automatically, allowing different ranks per component?
Source: Compressive learning for patch-based image denoising. §5.2, PDF p.13; §7, p.22.
Research direction. Can compressive patch models extend to generalized Gaussian mixtures, other inverse problems, and video denoising?
Source: Sketched learning for image denoising; Compressive learning for patch-based image denoising. §2.1, PDF p.4; §7, PDF p.22 respectively.
Open question. Which sketching operators permit recovery of general neural-network-parametrized distributions?
Source: Compressive learning of deep regularization for denoising. Conclusion, PDF p.12.
Research direction. Can batch-less deep compressive learning scale to larger patches and other linear inverse problems?
Source: Batch-less stochastic gradient descent for compressive learning of deep regularization for image denoising. PDF pp.11–13.

Image decomposition

Open question. What identifiability and incoherence theory supports gradient-sparse plus low-patch-rank decomposition?
Source: Adaptive parameter selection for gradient-sparse + low patch-rank recovery: application to image decomposition. §IV, PDF p.6.
Open question. Can convergence of the adaptive parameter-selection scheme be proved?
Source: Adaptive parameter selection for gradient-sparse + low patch-rank recovery: application to image decomposition. §IV, PDF p.6.
Research direction. Can the tuning strategy be extended to other decomposition models, such as the block nuclear-norm model?
Source: Adaptive parameter selection for gradient-sparse + low patch-rank recovery: application to image decomposition. §IV, PDF p.6.
Research direction. Can learned joint low-dimensional regularizers receive recovery guarantees for broader inverse problems?
Source: Joint structure-texture low dimensional modeling for image decomposition with a plug and play framework. §7, PDF pp.23–24.
Research direction. Can the joint model use piecewise-continuous structures, dictionary-sparse or mixed textures, and texture datasets?
Source: Joint structure-texture low dimensional modeling for image decomposition with a plug and play framework. §7, PDF p.24.
Research direction. Can joint learning handle three or more components, such as jump–oscillation–trend decompositions?
Source: Joint structure-texture low dimensional modeling for image decomposition with a plug and play framework. §7, PDF p.24.
Research direction. Can learned convex or variational generative priors reduce the computation and memory cost of joint decomposition?
Source: Joint structure-texture low dimensional modeling for image decomposition with a plug and play framework. §7, PDF p.24.

Historical questions and later follow-ups

These questions were raised in earlier papers and received subsequent answers or partial answers under specified assumptions.

Historical question. Is ℓ₁ optimal beyond weighted ℓ₁ norms, and is the nuclear norm analogously optimal?
Source: Optimality of 1-norm regularization among weighted 1-norms for sparse recovery: a case study on how to find optimal regularizations; Is the 1-norm the best convex sparse regularization?. Conclusions.
Follow-up: Later A theory of optimal convex regularization for low-dimensional recovery proves optimality among coercive continuous convex regularizers for specified RIP criteria, with stated model restrictions.
Historical question. Can over-parameterized off-grid projected gradient descent receive theoretical recovery guarantees?
Source: Fast off-the-grid sparse recovery with over-parametrized projected gradient descent. §IV, PDF p.5.
Follow-up: Addressed in a specified setting by Estimation of off-the-grid sparse spikes with over-parametrized projected gradient descent: theory and application; practical initialization and projection assumptions still matter.
Historical question. Can strong basins and geometric convergence be characterized for general parametrized low-dimensional models?
Source: The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension. Introduction, PDF p.4.
Follow-up: Later On strong basins of attractions for non-convex sparse spike estimation: upper and lower bounds advances the sparse-spike case; broader models remain separate.
Historical question. Can information preservation by compressive k-means sketches be proved?
Source: Compressive K-means. §5, PDF p.4.
Follow-up: Later Compressive Statistical Learning with Random Feature Moments and Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling establish guarantees under specified assumptions.
Historical question. Can deep compressive learning avoid high-dimensional grid discretization and use fast sketching?
Source: Compressive learning of deep regularization for denoising. Conclusion, PDF p.12.
Follow-up: Batch-less SGD in Batch-less stochastic gradient descent for compressive learning of deep regularization for image denoising addresses the grid obstacle; scaling remains relevant.
Historical question. Can neural motion prediction trained on the collected data improve sports action tracking?
Source: Piecewise linear prediction model for action tracking in sports. Conclusion, PDF pp.5–6.
Follow-up: Followed up directly by the CNN tracking method in Real-time multi-sport action tracking with convolutional neural networks.