Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Simple Algorithm for Approximation by Nomographic Functions
106
0
0.0
(
0
)
Added by
Steffen Limmer
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper introduces a novel algorithmic solution for the approximation of a given multivariate function by a nomographic function that is composed of a one-dimensional continuous and monotone outer function and a sum of univariate continuous inner functions. We show that a suitable approximation can be obtained by solving a cone-constrained Rayleigh-Quotient optimization problem. The proposed approach is based on a combination of a dimensionwise function decomposition known as Analysis of Variance (ANOVA) and optimization over a class of monotone polynomials. An example is given to show that the proposed algorithm can be applied to solve problems in distributed function computation over multiple-access channels.
rate research
Read More
In this paper, a clustered wireless sensor network is considered that is modeled as a set of coupled Gaussian multiple-access channels. The objective of the network is not to reconstruct individual sensor readings at designated fusion centers but rather to reliably compute some functions thereof. Our particular attention is on real-valued functions that can be represented as a post-processed sum of pre-processed sensor readings. Such functions are called nomographic functions and their special structure permits the utilization of the interference property of the Gaussian multiple-access channel to reliably compute many linear and nonlinear functions at significantly higher rates than those achievable with standard schemes that combat interference. Motivated by this observation, a computation scheme is proposed that combines a suitable data pre- and post-processing strategy with a nested lattice code designed to protect the sum of pre-processed sensor readings against the channel noise. After analyzing its computation rate performance, it is shown that at the cost of a reduced rate, the scheme can be extended to compute every continuous function of the sensor readings in a finite succession of steps, where in each step a different nomographic function is computed. This demonstrates the fundamental role of nomographic representations.
We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
A simple method is proposed for use in a scenario involving a single-antenna source node communicating with a destination node that is equipped with two antennas via multiple single-antenna relay nodes, where each relay is subject to an individual power constraint. Furthermore, ultra-reliable and low-latency communication are desired. The latter requirement translates to considering only schemes that make use of local channel state information. Whereas for a receiver equipped with a single antenna, distributed beamforming is a well known and adequate solution, no straightforward extension is known. In this paper, a scheme is proposed based on a space-time diversity transformation that is applied as a front-end operation at the destination node. This results in an effective unitary channel matrix replacing the scalar coefficient corresponding to each user. Each relay node then inverts its associated channel matrix, which is the generalization of undoing the channel phase in the classical case of distributed beamforming to a single-antenna receiver, and then repeats the message over the resulting gain-only channel. In comparison to a single-antenna destination node, the method doubles the diversity order without requiring any channel state information at the receiver while at the same time retaining the array gain offered by the relays.
A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w: V(G) to mathbb{Q}_{geq 0}$, the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices $X$ such that $G-X$ is a split graph. It is easy to show that a graph is a split graph if and only it it does not contain a $4$-cycle, $5$-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy $5$-approximation algorithm. On the other hand, for every $delta >0$, SVD does not admit a $(2-delta)$-approximation algorithm, unless P=NP or the Unique Games Conjecture fails. For every $epsilon >0$, Lokshtanov, Misra, Panolan, Philip, and Saurabh recently gave a randomized $(2+epsilon)$-approximation algorithm for SVD. In this work we give an extremely simple deterministic $(2+epsilon)$-approximation algorithm for SVD.
Cognitive radio that supports a secondary and opportunistic access to licensed spectrum shows great potential to dramatically improve spectrum utilization. Spectrum sensing performed by secondary users to detect unoccupied spectrum bands, is a key enabling technique for cognitive radio. This paper proposes a truncated sequential spectrum sensing scheme, namely the sequential shifted chi-square test (SSCT). The SSCT has a simple test statistic and does not rely on any deterministic knowledge about primary signals. As figures of merit, the exact false-alarm probability is derived, and the miss-detection probability as well as the average sample number (ASN) are evaluated by using a numerical integration algorithm. Corroborating numerical examples show that, in comparison with fixed-sample size detection schemes such as energy detection, the SSCT delivers considerable reduction on the ASN while maintaining a comparable detection performance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
