Oversampling analysis in fractional Fourier domain

Oversampling is widely used in practical applications of digital signal processing. As the fractional Fourier transform has been developed and applied in signal processing fields, it is necessary to consider the oversampling theorem in the fractional Fourier domain. In this paper, the oversampling theorem in the fractional Fourier domain is analyzed. The fractional Fourier spectral relation between the original oversampled sequence and its subsequences is derived first, and then the expression for exact reconstruction of the missing samples in terms of the subsequences is obtained. Moreover, by taking a chirp signal as an example, it is shown that, reconstruction of the missing samples in the oversampled signal is suitable in the fractional Fourier domain for the signal whose time-frequency distribution has the minimum support in the fractional Fourier domain. Supported partially by the National Natural Science Foundation of China for Distinguished Young Scholars (Grant No. 60625104), the National Natural Science Foundation of China (Grant Nos. 60890072, 60572094), and the National Basic Research Program of China (Grant No. 2009CB724003)     

Construction and enumeration of Boolean functions with maximum algebraic immunity

Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also given. For a given function p(x) with deg(p(x)) < , we give a method to construct functions in the form p(x)+q(x) which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q(x) has degree no less than . Supported by the National Natural Science Foundation of China (Grant No. 60673068), and the Natural Science Foundation of Shandong Province (Grant Nos. Y2007G16, Y2008G01)     

Lower estimation of approximation rate for neural networks

Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T...     

Loop Subdivision Surface Based Progressive Interpolation

A new method for constructing interpolating Loop subdivision surfaces is presented. The new method is an extension of the progressive interpolation technique for B-splines. Given a triangular mesh M, the idea is to iteratively upgrade the vertices of M to generate a new control mesh M such that limit surface of M would interpolate M. It can be shown that the iterative process is convergent for Loop subdivision surfaces. Hence, the method is well-defined. The new method has the advantages of both a local ...     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence     

Fractional differential approach to detecting textural features of digital image and its fractional differential filter implementation

This paper mainly discusses fractional differential approach to detecting textural features of digital image and its fractional differential filter. Firstly, both the geo- metric meaning and the kinetic physical meaning of fractional differential are clearly explained in view of information theory and kinetics, respectively. Secondly, it puts forward and discusses the definitions and theories of fractional stationary point, fractional equilibrium coefficient, fractional stable coefficient, and fractional grayscale co-occurrence matrix. At the same time, it particularly discusses frac- tional grayscale co-occurrence matrix approach to detecting textural features of digital image. Thirdly, it discusses in detail the structures and parameters of nxn any order fractional differential mask on negative x-coordinate, positive x-coordi- nate, negative y-coordinate, positive y-coordinate, left downward diagonal, left upward diagonal, right downward diagonal, and right upward diagonal, respectively. Furthermore, it discusses the numerical implementation algorithms of fractional differential mask for digital image. Lastly, based on the above-mentioned discus- sion, it puts forward and discusses the theory and implementation of fractional differential filter for digital image. Experiments show that the fractional differential-based image operator has excellent feedback for enhancing the textural details of rich-grained digital images.     

A note on relativized log space

It is shown that there is a recursive oracleD such that, thereby answering an open question of Ladner and Lynch [5]. Here and denote the class of languages accepted in deterministic, respectively nondeterministic, space logn. This work was supported by NSF Grant MCS-8001963.     

Hierarchical matrix preconditioners for the Oseen equations

Hierarchical matrices provide a technique for the data-sparse approximation and matrix arithmetic of large, fully populated matrices. In particular, approximate inverses as well as approximate LU factorizations of finite element stiffness matrices may be computed and stored in nearly optimal complexity. In this paper, we develop efficient -matrix preconditioners for the Oseen equations. In particular, -matrices will provide efficient preconditioners for the auxiliary (scalar) discrete convection–diffusion and pressure Schur complement problems. We will provide various numerical tests comparing the resulting preconditioners with each other. This work was supported in part by the US Department of Energy under Grant No. DE-FG02-04ER25649 and in part by the National Science Foundation under grant No. DMS-0408950.     

Almost direct sum decomposition and implementation of 2D behaviors

This paper deals with multidimensional systems, for example, systems described by linear, constant coefficient partial differential/difference equations. In the behavioral approach, the notion of interconnection is the basis of control. In this setting, feedback interconnection of systems is based on the still more fundamental concept of regular interconnection, which has been introduced by J.C. Willems. The dual problem of regular interconnection is the one of direct sum decomposition. The following two problems are addressed: given a behavior and one of its sub-behaviors , under what conditions does there exist another sub-behavior such that has finite dimension and has finite codimension with respect to i.e. we treat the direct sum decomposition of up to finite-dimensional behaviors, which, in this context, are considered negligible. The second related problem concerns regular interconnections and reads as follows: given a plant behavior together with a desired behavior, find, if possible, another behavior (a controller) such that the interconnection is regular and has finite codimension with respect to the given desired behavior. A constructive solution to the problems is provided for two-dimensional behaviors.     

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

We study the quantum complexity class \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\), which is an affirmative answer to the question posed by Høyer and ?palek. In sharp contrast to the strict hierarchy of the classical complexity classes: \({\mathsf{NC}^{0} \subsetneq \mathsf{AC}^{0} \subsetneq \mathsf{TC}^{0}}\), our result with Høyer and ?palek’s one implies the collapse of the hierarchy of the corresponding quantum ones: \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}=\mathsf{QAC}^\mathsf{0}_\mathsf{f}=\mathsf{QTC}^\mathsf{0}_\mathsf{f}}\). Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) and \({\mathsf{QTC}^\mathsf{0}_\mathsf{f}}\) circuits for implementing the same operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\), there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) circuit with gates for the quantum Fourier transform.     

Research progress on discretization of fractional Fourier transform

As the fractional Fourier transform has attracted a considerable amount of attention in the area of optics and signal processing, the discretization of the fractional Fourier transform becomes vital for the application of the fractional Fourier transform. Since the discretization of the fractional Fourier transform cannot be obtained by directly sampling in time domain and the fractional Fourier domain, the discretization of the fractional Fourier transform has been investigated recently. A summary of discretizations of the fractional Fourier transform developed in the last nearly two decades is presented in this paper. The discretizations include sampling in the fractional Fourier domain, discrete-time fractional Fourier transform, fractional Fourier series, discrete fractional Fourier transform （including 3 main types： linear combination-type; sampling-type; and eigen decomposition-type）, and other discrete fractional signal transform. It is hoped to offer a doorstep for the readers who are interested in the fractional Fourier transform.     

基于FFT和FRFT的非平稳干扰估计和抑制

提出了一个基于快速傅里叶变换(FFT)和分数阶傅里叶变换(FRFT)的线性频率调制(LFM)干扰参数的估计和抑制方法.通过FFT粗略估计和FRFT精确估计,确定LFM干扰在分数阶傅里叶域所处的旋转角度,估计出LFM的相关参数,利用最小二乘法综合出LFM干扰信号;然后从接收的信号中减去,有效地抑制LFM干扰.性能仿真分析表明,该方法较好地改善了误码率性能,降低了计算的复杂度,提高了系统处理的实时性.     

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given strongly connected directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-hard to tell whether it can be extended. The latter result implies, in particular, that for a given set of points , it is NP-hard to generate all maximal subsets of contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem. This research was supported by the National Science Foundation (Grant IIS-0118635). The third and fourth authors are also grateful for the partial support by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. Our friend and co-author, Leonid Khachiyan tragically passed away on April 29, 2005.     

基于FRFT的线性调频信号映射方法的快速算法

针对基于分数傅立叶变换(Fractional Fourier transform，FRFT)的线性调频信号(LFM)的参数估计方法，提出了基于Radon变换的判决准则，并建立了相应的快速算法。该映射方法将具有同样调频斜率、同样多普勒中心频率、不同初始相位的信号映射到同一个点。该快速算法的计算量等同于FRFT的计算量，计算结果的精确度取决于连续两次的FRFT运算。     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

Universal asynchronous iterative arrays of Mealy automata

Summary Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton, , with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine, such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once. contains only four states and one input and output for each direction.     

A novel fractional wavelet transform and its applications

The wavelet transform (WT) and the fractional Fourier transform (FRFT) are powerful tools for many applications in the field of signal processing.However,the signal analysis capability of the former is limited in the time-frequency plane.Although the latter has overcome such limitation and can provide signal representations in the fractional domain,it fails in obtaining local structures of the signal.In this paper,a novel fractional wavelet transform (FRWT) is proposed in order to rectify the limitations of the WT and the FRFT.The proposed transform not only inherits the advantages of multiresolution analysis of the WT,but also has the capability of signal representations in the fractional domain which is similar to the FRFT.Compared with the existing FRWT,the novel FRWT can offer signal representations in the time-fractional-frequency plane.Besides,it has explicit physical interpretation,low computational complexity and usefulness for practical applications.The validity of the theoretical derivations is demonstrated via simulations.     

一种新型分数阶小波变换及其应用

小波变换和分数Fourier变换是应用非常广泛的信号处理工具.但是,小波变换仅局限于时频域分析信号;分数Fourier变换虽突破了时频域局限能够在分数域分析信号,却无法表征信号局部特征.为此,提出了一种新型分数阶小波变换,该变换不但继承了小波变换多分辨分析的优点,而且具有分数Fourier变换分数域表征功能.与现有分数阶小波变换相比,新型分数阶小波变换可以实现对信号在时间-分数频域的多分辨分析.此外,该变换具有物理意义明确和计算复杂度低的优点,更有利于满足实际应用需求.最后,通过仿真实验验证了所提理论的有效性.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.