A numerical exploration of compressed sampling recovery

This paper explores numerically the efficiency of ?¹ minimization for the recovery of sparse signals from compressed sampling measurements in the noiseless case. This numerical exploration is driven by a new greedy pursuit algorithm that computes sparse vectors that are difficult to recover by ?¹ minimization. The supports of these pathological vectors are also used to select sub-matrices that are ill-conditioned. This allows us to challenge theoretical identifiability criteria based on polytopes analysis and on restricted isometry conditions. We evaluate numerically the theoretical analysis without resorting to Monte-Carlo sampling, which tends to avoid worst case scenarios.     

New exact homoclinic wave and periodic wave solutions for the Ginzburg-Landau equation

New exact solutions including homoclinic wave and periodic wave solutions for the 2D Ginzburg-Landau equation are obtained using the auxiliary function method and the -expansion method, respectively. The solutions are expressed by the hyperbolic functions and the trigonometric functions. There result shows that there exists a kink wave solution which tends to one and the same periodic wave solution as time tends to infinite.     

A note on exact complex travelling wave solutions for (2+1)-dimensional B-type Kadomtsev-Petviashvili equation

The -expansion method can be used for constructing exact travelling wave solutions of real nonlinear evolution equations. In this paper, we improve the -expansion method and explore new application of this method to (2+1)-dimensional B-type Kadomtsev-Petviashvili (BKP) equation. New types of exact complex travelling wave solutions of (2+1)-dimensional BKP equation are found. Some exact solutions of (2+1)-dimensional BKP equation obtained before are special cases of our results in this paper.     

A system of mixed equilibrium problems, fixed point problems of strictly pseudo-contractive mappings and nonexpansive semi-groups

The purpose of this paper is to introduce an iterative algorithm for finding a common element of the set of solutions for a system of mixed equilibrium problems, the set of common fixed points for an infinite family of strictly pseudo-contractive mappings and the set of common fixed points for nonexpansive semi-groups in Hilbert space. Under suitable conditions some strong convergence theorem are proved. The results presented in the paper extend and improve some recent results.     

Convergence theorems for equilibrium problem, variational inequality problem and countably infinite relatively quasi-nonexpansive mappings

In this paper, we introduce an iterative process which converges strongly to a common element of set of common fixed points of countably infinite family of closed relatively quasi- nonexpansive mappings, the solution set of generalized equilibrium problem and the solution set of the variational inequality problem for a γ-inverse strongly monotone mapping in Banach spaces. Our theorems improve, generalize, unify and extend several results recently announced.     

Soliton solutions of a BBM(m, n) equation with generalized evolution

We consider a BBM(m, n) equation which is a generalization of the celebrated Benjamin-Bona-Mahony equation with generalized evolution term. By using two solitary wave ansatze in terms of sech^p(x) and tanh^p(x) functions, we find exact analytical bright and dark soliton solutions for the considered model. The physical parameters in the soliton solutions are obtained as function of the dependent model coefficients. The conditions of existence of solitons are presented. Note that, it is always useful and desirable to construct exact analytical solutions especially soliton-type envelope for the understanding of most nonlinear physical phenomena.     

The induced path function, monotonicity and betweenness

The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský [20]. Surprisingly, Nebeský [23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if w∈J(u,v), with w≠u, implies u∉J(w,v) and x∈J(u,v) implies J(u,x)⊆J(u,v). It is monotone if x,y∈J(u,v) implies J(x,y)⊆J(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.     

A note on the hardness of Skolem-type sequences

The purpose of this note is to give upper bounds (assuming different from ) on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. We prove that the existence questions for both multi-Skolem sequences and generalized Skolem sequences are strongly -complete. These results are significant strengthenings and simplifications of the recent -completeness result for generalized multi-Skolem sequences.     

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as , is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as , is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V,E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n^0.5−?) for any ?>0 unless NP=ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n^0.5−?) for any ?>0 unless NP=ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.