Parseval wavelets on hierarchical graphs

Wavelets on graphs have been studied for the past few years, and in particular, several approaches have been proposed to design wavelet transforms on hierarchical graphs. Although such methods are computationally efficient and easy to implement, their frames are highly restricted. In this paper, we propose a general framework for the design of wavelet transforms on hierarchical graphs. Our design is guaranteed to be a Parseval tight frame, which preserves the $l_2$ norm of any input signals. To demonstrate the potential usefulness of our approach, we perform several experiments, in which we learn a wavelet frame based on our framework, and show, in inpainting experiments, that it performs better than a Haar-like hierarchical wavelet transform and a learned treelet. We also show with category theory that the algebraic properties of the proposed transform have a strong relationship with those of the hierarchical graph that represents the structure of the given data.     

Conditional p-adic probability logic

In this paper we present the proof-theoretical approach to p-adic valued conditional probabilistic logics. We introduce two such logics denoted by ${\mathit{CPL}}_{{\mathbf{Z}}_{\mathbf{p}}}$ and ${\mathit{CPL}}_{{\mathbf{Q}}_{\mathbf{p}}}^{\mathit{fin}}$. Each of these logics extends classical propositional logic with a list of binary (conditional probability) operators. Formulas are interpreted in Kripke-like models that are based on p-adic probability spaces. Axiomatic systems with infinitary rules of inference are given and proved to be sound and strongly complete. The decidability of the satisfiability problem for each logic is proved.     

Multi-set neighbor distinguishing 3-edge coloring

Let $G$ be a graph without isolated edges, and let $c:E\left(G\right)\to \{1,\dots ,k\}$ be a coloring of the edges, where adjacent edges may be colored the same. The color code of a vertex $v$ is the ordered $k$-tuple $(a_1,a_2,\dots ,a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$. If every two adjacent vertices of $G$ have different color codes, such a coloring is called multi-set neighbor distinguishing. In this paper, we prove that three colors are sufficient to produce a multi-set neighbor distinguishing edge coloring for every graph without isolated edges.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

A generalization of Hungarian method and Hall’s theorem with applications in wireless sensor networks

In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall’s marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum $g$-quasi-matching (that is a set $F$ of edges in a bipartite graph such that in one set of the bipartition every vertex $v$ has at least $g\left(v\right)$ incident edges from $F$, where $g$ is a so-called need mapping, while on the other side of the bipartition the distribution of degrees with respect to $F$ is lexicographically minimum). We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement: the optima of any component-based strictly convex cost function on any subset of $L_1$-sphere in ${\mathbb{N}}^n$ are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks.     

Extreme value analysis of empirical frame coefficients and implications for denoising by soft-thresholding

Denoising by frame thresholding is one of the most basic and efficient methods for recovering a discrete signal or image from data that are corrupted by additive Gaussian white noise. The basic idea is to select a frame of analyzing elements that separates the data in few large coefficients due to the signal and many small coefficients mainly due to the noise ${ϵ}_n$. Removing all data coefficients being in magnitude below a certain threshold yields a reconstruction of the original signal. In order to properly balance the amount of noise to be removed and the relevant signal features to be kept, a precise understanding of the statistical properties of thresholding is important. For that purpose we derive the asymptotic distribution of ${\max }_{\omega \in {\Omega }_n}|〈{\varphi }_{\omega }^n,{ϵ}_n〉|$ for a wide class of redundant frames $({\varphi }_{\omega }^n:\omega \in {\Omega }_n)$. Based on our theoretical results we give a rationale for universal extreme value thresholding techniques yielding asymptotically sharp confidence regions and smoothness estimates corresponding to prescribed significance levels. The results cover many frames used in imaging and signal recovery applications, such as redundant wavelet systems, curvelet frames, or unions of bases. We show that ‘generically’ a standard Gumbel law results as it is known from the case of orthonormal wavelet bases. However, for specific highly redundant frames other limiting laws may occur. We indeed verify that the translation invariant wavelet transform shows a different asymptotic behaviour.     

Dyadic representations of graphs

A graph $G$ is dyadic provided it has a representation $v\to S_v$ from vertices $v$ of $G$ to subtrees $S_v$ of a host tree $T$ with maximum degree 3 such that $\left(i\right)$$v$ and $w$ are adjacent in $G$ if and only if $S_v$ and $S_w$ share at least three nodes and $\left(ii\right)$ each edge of $T$ is used by exactly two representing subtrees. We show that a connected graph is dyadic if and only if it can be constructed from edges and cycles by gluing vertices to vertices and edges to edges.