Zhiqiang Xu

Guangwu Xu, Zhiqiang Xu

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included.

Zhiqiang Xu

One can recover sparse multivariate trigonometric polynomials from few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling of multivariate trigonometric polynomials inspired by Weil's exponential sum. Our sampling can produce a deterministic matrix satisfying the statistical restricted isometry property, and also nearly optimal Grassmannian frames. We show that one can exactly reconstruct every $M$-sparse multivariate trigonometric polynomial with fixed degree and of length $D$ from the determinant sampling $X$, using the orthogonal matching pursuit, and $# X$ is a prime number greater than $(M\log D)^2$. This result is almost optimal within the $(\log D)^2 $ factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.

Bin Han, Zhiqiang Xu

In this paper we study the robustness properties of dimensionality reduction with Gaussian random matrices having arbitrarily erased rows. We first study the robustness property against erasure for the almost norm preservation property of Gaussian random matrices by obtaining the optimal estimate of the erasure ratio for a small given norm distortion rate. As a consequence, we establish the robustness property of Johnson-Lindenstrauss lemma and the robustness property of restricted isometry property with corruption for Gaussian random matrices. Secondly, we obtain a sharp estimate for the optimal lower and upper bounds of norm distortion rates of Gaussian random matrices under a given erasure ratio. This allows us to establish the strong restricted isometry property with the almost optimal RIP constants, which plays a central role in the study of phaseless compressed sensing.

Zhiqiang Xu

In this paper, we use multivariate splines to investigate the volume of polytopes. We first present an explicit formula for the multivariate truncated power, which can be considered as a dual version of the famous Brion's formula for the volume of polytopes. We also prove that the integration of polynomials over polytopes can be dealt with by the multivariate truncated power. Moreover, we show that the volume of the cube slicing can be considered as the maximum value of the box spline. Based on this connection, we give a simple proof for Good's conjecture, which has been settled by probability methods.

Meng Huang, Zhiqiang Xu

We consider the rank minimization problem from quadratic measurements, i.e., recovering a rank $r$ matrix $X \in \mathbb{R}^{n \times r}$ from $m$ scalar measurements $y_i=a_i^{\top} XX^{\top} a_i,\;a_i\in \mathbb{R}^n,\;i=1,\ldots,m$. Such problem arises in a variety of applications such as quadratic regression and quantum state tomography. We present a novel algorithm, which is termed exponential-type gradient descent algorithm, to minimize a non-convex objective function $f(U)=\frac{1}{4m}\sum_{i=1}^m(y_i-a_i^{\top} UU^{\top} a_i)^2$. This algorithm starts with a careful initialization, and then refines this initial guess by iteratively applying exponential-type gradient descent. Particularly, we can obtain a good initial guess of $X$ as long as the number of Gaussian random measurements is $O(nr)$, and our iteration algorithm can converge linearly to the true $X$ (up to an orthogonal matrix) with $m=O\left(nr\log (cr)\right)$ Gaussian random measurements.

Artūras Dubickas, Zhiqiang Xu

In this paper, we exploit the relation between the regularity of refinable functions with non-integer dilations and the distribution of powers of a fixed number modulo 1, and show the nonexistence of a non-trivial {\bf C}^{\infty} solution of the refinement equation with non-integer dilations. Using this, we extend the results on the refinable splines with non-integer dilations and construct a counterexample to some conjecture concerning the refinable splines with non-integer dilations. Finally, we study the box splines satisfying the refinement equation with non-integer dilation and translations. Our study involves techniques from number theory and harmonic analysis.

Yang Wang, Zhiqiang Xu

The regularity of refinable functions has been studied extensively in the past. A classical result by Daubechies and Lagarias states that a compactly supported refinable function in $\R$ of finite mask with integer dilation and translations cannot be in $C^\infty$. A bound on the regularity based on the eigenvalues of certain matrices associated with the refinement equation is also given. Surprisingly this fundamental classical result has not been proved in the more general settings, such as in higher dimensions or when the dilation is not an integer. In this paper we extend this classical result to the most general setting for arbitrary dimension, dilation and translations.

Zhiqiang Xu

In this note, we investigate the theoretical properties of Orthogonal Matching Pursuit (OMP), a class of decoder to recover sparse signal in compressed sensing. In particular, we show that the OMP decoder can give $(p,q)$ instance optimality for a large class of encoders with $1\leq p\leq q \leq 2$ and $(p,q)\neq (2,2)$. We also show that, if the encoding matrix is drawn from an appropriate distribution, then the OMP decoder is $(2,2)$ instance optimal in probability.

Peng Tang, Zhiqiang Xu, Pengfei Wei et al.

We propose an efficient deep learning method for single image defocus deblurring (SIDD) by further exploring inverse kernel properties. Although the current inverse kernel method, i.e., kernel-sharing parallel atrous convolution (KPAC), can address spatially varying defocus blurs, it has difficulty in handling large blurs of this kind. To tackle this issue, we propose a Residual and Recursive Kernel-sharing Atrous Convolution (R$^2$KAC). R$^2$KAC builds on a significant observation of inverse kernels, that is, successive use of inverse-kernel-based deconvolutions with fixed size helps remove unexpected large blurs but produces ringing artifacts. Specifically, on top of kernel-sharing atrous convolutions used to simulate multi-scale inverse kernels, R$^2$KAC applies atrous convolutions recursively to simulate a large inverse kernel. Specifically, on top of kernel-sharing atrous convolutions, R$^2$KAC stacks atrous convolutions recursively to simulate a large inverse kernel. To further alleviate the contingent effect of recursive stacking, i.e., ringing artifacts, we add identity shortcuts between atrous convolutions to simulate residual deconvolutions. Lastly, a scale recurrent module is embedded in the R$^2$KAC network, leading to SR-R$^2$KAC, so that multi-scale information from coarse to fine is exploited to progressively remove the spatially varying defocus blurs. Extensive experimental results show that our method achieves the state-of-the-art performance.

Buhua Liu, Shitong Shao, Bao Li et al.

Diffusion models have emerged as the leading paradigm in generative modeling, excelling in various applications. Despite their success, these models often misalign with human intentions and generate results with undesired properties or even harmful content. Inspired by the success and popularity of alignment in tuning large language models, recent studies have investigated aligning diffusion models with human expectations and preferences. This work mainly reviews alignment of diffusion models, covering advancements in fundamentals of alignment, alignment techniques of diffusion models, preference benchmarks, and evaluation for diffusion models. Moreover, we discuss key perspectives on current challenges and promising future directions on solving the remaining challenges in alignment of diffusion models. To the best of our knowledge, our work is the first comprehensive review paper for researchers and engineers to comprehend, practice, and research alignment of diffusion models.

Meng Huang, Yuxuan Pang, Zhiqiang Xu

In this paper, we study the restricted isometry property of partial random circulant matrices. For a bounded subgaussian generator with independent entries, we prove that the partial random circulant matrices satisfy $s$-order RIP with high probability if one chooses $m\gtrsim s \log^2(s)\log (n)$ rows randomly where $n$ is the vector length. This improves the previously known bound $m \gtrsim s \log^2 s\log^2 n$.

Chengqian Gao, Haonan Li, Liu Liu et al.

The alignment of large language models (LLMs) often assumes that using more clean data yields better outcomes, overlooking the match between model capacity and example difficulty. Challenging this, we propose a new principle: Preference data vary in difficulty, and overly difficult examples hinder alignment, by exceeding the model's capacity. Through systematic experimentation, we validate this principle with three key findings: (1) preference examples vary in difficulty, as evidenced by consistent learning orders across alignment runs; (2) overly difficult examples significantly degrade performance across four LLMs and two datasets; and (3) the capacity of a model dictates its threshold for handling difficult examples, underscoring a critical relationship between data selection and model capacity. Building on this principle, we introduce Selective DPO, which filters out overly difficult examples. This simple adjustment improves alignment performance by 9-16% in win rates on the AlpacaEval 2 benchmark compared to the DPO baseline, suppressing a series of DPO variants with different algorithmic adjustments. Together, these results illuminate the importance of aligning data difficulty with model capacity, offering a transformative perspective for improving alignment strategies in LLMs. Code is available at https://github.com/glorgao/SelectiveDPO.

Zhiqiang Xu

In this paper, we recast a special case of Mahler'c conjecture by the maximum value of box splines. This is the case of polytopes with at most $2n+2$ facets. An asymptotic formula for univariate box splines is given. Based on the formula, Mahler's conjecture is proved in this case provided $n$ is big enough.

Zikai Zhou, Shitong Shao, Lichen Bai et al.

Text-to-image diffusion model is a popular paradigm that synthesizes personalized images by providing a text prompt and a random Gaussian noise. While people observe that some noises are ``golden noises'' that can achieve better text-image alignment and higher human preference than others, we still lack a machine learning framework to obtain those golden noises. To learn golden noises for diffusion sampling, we mainly make three contributions in this paper. First, we identify a new concept termed the \textit{noise prompt}, which aims at turning a random Gaussian noise into a golden noise by adding a small desirable perturbation derived from the text prompt. Following the concept, we first formulate the \textit{noise prompt learning} framework that systematically learns ``prompted'' golden noise associated with a text prompt for diffusion models. Second, we design a noise prompt data collection pipeline and collect a large-scale \textit{noise prompt dataset}~(NPD) that contains 100k pairs of random noises and golden noises with the associated text prompts. With the prepared NPD as the training dataset, we trained a small \textit{noise prompt network}~(NPNet) that can directly learn to transform a random noise into a golden noise. The learned golden noise perturbation can be considered as a kind of prompt for noise, as it is rich in semantic information and tailored to the given text prompt. Third, our extensive experiments demonstrate the impressive effectiveness and generalization of NPNet on improving the quality of synthesized images across various diffusion models, including SDXL, DreamShaper-xl-v2-turbo, and Hunyuan-DiT. Moreover, NPNet is a small and efficient controller that acts as a plug-and-play module with very limited additional inference and computational costs, as it just provides a golden noise instead of a random noise without accessing the original pipeline.

Lichen Bai, Shitong Shao, Zikai Zhou et al.

Diffusion models, the most popular generative paradigm so far, can inject conditional information into the generation path to guide the latent towards desired directions. However, existing text-to-image diffusion models often fail to maintain high image quality and high prompt-image alignment for those challenging prompts. To mitigate this issue and enhance existing pretrained diffusion models, we mainly made three contributions in this paper. First, we propose diffusion self-reflection that alternately performs denoising and inversion and demonstrate that such diffusion self-reflection can leverage the guidance gap between denoising and inversion to capture prompt-related semantic information with theoretical and empirical evidence. Second, motivated by theoretical analysis, we derive Zigzag Diffusion Sampling (Z-Sampling), a novel self-reflection-based diffusion sampling method that leverages the guidance gap between denosing and inversion to accumulate semantic information step by step along the sampling path, leading to improved sampling results. Moreover, as a plug-and-play method, Z-Sampling can be generally applied to various diffusion models (e.g., accelerated ones and Transformer-based ones) with very limited coding and computational costs. Third, our extensive experiments demonstrate that Z-Sampling can generally and significantly enhance generation quality across various benchmark datasets, diffusion models, and performance evaluation metrics. For example, DreamShaper with Z-Sampling can self-improve with the HPSv2 winning rate up to 94% over the original results. Moreover, Z-Sampling can further enhance existing diffusion models combined with other orthogonal methods, including Diffusion-DPO.

Dezhong Yao, Yuexin Shi, Tongtong Liu et al.

Federated Learning (FL) is increasingly adopted in edge computing scenarios, where a large number of heterogeneous clients operate under constrained or sufficient resources. The iterative training process in conventional FL introduces significant computation and communication overhead, which is unfriendly for resource-constrained edge devices. One-shot FL has emerged as a promising approach to mitigate communication overhead, and model-heterogeneous FL solves the problem of diverse computing resources across clients. However, existing methods face challenges in effectively managing model-heterogeneous one-shot FL, often leading to unsatisfactory global model performance or reliance on auxiliary datasets. To address these challenges, we propose a novel FL framework named FedMHO, which leverages deep classification models on resource-sufficient clients and lightweight generative models on resource-constrained devices. On the server side, FedMHO involves a two-stage process that includes data generation and knowledge fusion. Furthermore, we introduce FedMHO-MD and FedMHO-SD to mitigate the knowledge-forgetting problem during the knowledge fusion stage, and an unsupervised data optimization solution to improve the quality of synthetic samples. Comprehensive experiments demonstrate the effectiveness of our methods, as they outperform state-of-the-art baselines in various experimental setups.

Zhengquan Luo, Zhiqiang Xu

Dataset distillation (DD) aims to construct compact synthetic datasets that allow models to achieve comparable performance to full-data training while substantially reducing storage and computation. Despite rapid empirical progress, its theoretical foundations remain limited: existing methods (gradient, distribution, trajectory matching) are built on heterogeneous surrogate objectives and optimization assumptions, which makes it difficult to analyze their common principles or provide general guarantees. Moreover, it is still unclear under what conditions distilled data can retain the effectiveness of full datasets when the training configuration, such as optimizer, architecture, or augmentation, changes. To answer these questions, we propose a unified theoretical framework, termed configuration--dynamics--error analysis, which reformulates major DD approaches under a common generalization-error perspective and provides two main results: (i) a scaling law that provides a single-configuration upper bound, characterizing how the error decreases as the distilled sample size increases and explaining the commonly observed performance saturation effect; and (ii) a coverage law showing that the required distilled sample size scales linearly with configuration diversity, with provably matching upper and lower bounds. In addition, our unified analysis reveals that various matching methods are interchangeable surrogates, reducing the same generalization error, clarifying why they can all achieve dataset distillation and providing guidance on how surrogate choices affect sample efficiency and robustness. Experiments across diverse methods and configurations empirically confirm the derived laws, advancing a theoretical foundation for DD and enabling theory-driven design of compact, configuration-robust dataset distillation.

Heng Zhou, Zhiqiang Xu

The $p$-set, which is in a simple analytic form, is well distributed in unit cubes. The well-known Weil's exponential sum theorem presents an upper bound of the exponential sum over the $p$-set. Based on the result, one shows that the $p$-set performs well in numerical integration, in compressed sensing as well as in UQ. However, $p$-set is somewhat rigid since the cardinality of the $p$-set is a prime $p$ and the set only depends on the prime number $p$. The purpose of this paper is to present generalizations of $p$-sets, say $\mathcal{P}_{d,p}^{{\mathbf a},ε}$, which is more flexible. Particularly, when a prime number $p$ is given, we have many different choices of the new $p$-sets. Under the assumption that Goldbach conjecture holds, for any even number $m$, we present a point set, say ${\mathcal L}_{p,q}$, with cardinality $m-1$ by combining two different new $p$-sets, which overcomes a major bottleneck of the $p$-set. We also present the upper bounds of the exponential sums over $\mathcal{P}_{d,p}^{{\mathbf a},ε}$ and ${\mathcal L}_{p,q}$, which imply these sets have many potential applications.

Zhiqiang Xu

The paper presents several results that address a fundamental question in low-rank matrices recovery: how many measurements are needed to recover low rank matrices? We begin by investigating the complex matrices case and show that $4nr-4r^2$ generic measurements are both necessary and sufficient for the recovery of rank-$r$ matrices in $\C^{n\times n}$ by algebraic tools. Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound $4nr-4r^2$ is tight provided $n=2^k+r, k\in \Z_+$. Motivated by Vinzant's work, we construct $11$ matrices in $\R^{4\times 4}$ by computer random search and prove they define injective measurements on rank-$1$ matrices in $\R^{4\times 4}$. This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than $2n-1$ orthogonal projections are possible for the recovery of $x\in \R^n$ from the norm of them.

Zhiqiang Xu

The orthogonal multi-matching pursuit (OMMP) is a natural extension of orthogonal matching pursuit (OMP). We denote the OMMP with the parameter $M$ as OMMP(M) where $M\geq 1$ is an integer. The main difference between OMP and OMMP(M) is that OMMP(M) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit (OMMP) under RIP. In particular, we show that, when the measurement matrix A satisfies $(9s, 1/10)$-RIP, there exists an absolutely constant $M_0\leq 8$ so that OMMP(M_0) can recover $s$-sparse signal within $s$ iterations. We furthermore prove that, for slowly-decaying $s$-sparse signal, OMMP(M) can recover s-sparse signal within $O(\frac{s}{M})$ iterations for a large class of $M$. In particular, for $M=s^a$ with $a\in [0,1/2]$, OMMP(M) can recover slowly-decaying $s$-sparse signal within $O(s^{1-a})$ iterations. The result implies that OMMP can reduce the computational complexity heavily.

Zhiqiang Xu

Using methods developed in multivariate splines, we present an explicit formula for discrete truncated powers, which are defined as the number of non-negative integer solutions of linear Diophantine equations. We further use the formula to study some classical problems in discrete mathematics as follows. First, we extend the partition function of integers in number theory. Second, we exploit the relation between the relative volume of convex polytopes and multivariate truncated powers and give a simple proof for the volume formula for the Pitman-Stanley polytope. Third, an explicit formula for the Ehrhart quasi-polynomial is presented.

Zhiqiang Xu, Guoliang Xu

In this paper, several discrete schemes for Gaussian curvature are surveyed. The convergence property of a modified discrete scheme for the Gaussian curvature is considered. Furthermore, a new discrete scheme for Gaussian curvature is resented. We prove that the new scheme converges at the regular vertex with valence not less than 5. By constructing a counterexample, we also show that it is impossible for building a discrete scheme for Gaussian curvature which converges over the regular vertex with valence 4. Finally, asymptotic errors of several discrete scheme for Gaussian curvature are compared.