OpenRaiser/Intern-Atlas huggingface dataset:
A Quadratic Loss Multi-Class SVM
Venue: arXiv cs.LG 2008
Year: 2008

Using a support vector machine requires to set two types of hyperparameters: the soft margin parameter C and the parameters of the kernel. To perform this model selection task, the method of choice is cross-validation. Its leave-one-out variant is known to produce an estimator of the generalization error which is almost unbiased. Its major drawback rests in its time requirement. To overcome this difficulty, several upper bounds on the leave-one-out error of the pattern recognition SVM have been derived. Among those bounds, the most popular one is probably the radius-margin bound. It applies to the hard margin pattern recognition SVM, and by extension to the 2-norm SVM. In this report, we introduce a quadratic loss M-SVM, the M-SVM^2, as a direct extension of the 2-norm SVM to the multi-class case. For this machine, a generalized radius-margin bound is then established.
Joint Physical Layer Coding and Network Coding for Bi-Directional Relaying
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of two transmitters wishing to exchange information through a relay in the middle. The channels between the transmitters and the relay are assumed to be synchronized, average power constrained additive white Gaussian noise channels with a real input with signal-to-noise ratio (SNR) of snr. An upper bound on the capacity is 1/2 log(1+ snr) bits per transmitter per use of the medium-access phase and broadcast phase of the bi-directional relay channel. We show that using lattice codes and lattice decoding, we can obtain a rate of 1/2 log(0.5 + snr) bits per transmitter, which is essentially optimal at high SNRs. The main idea is to decode the sum of the codewords modulo a lattice at the relay followed by a broadcast phase which performs Slepian-Wolf coding with structured codes. For asymptotically low SNR's, jointly decoding the two transmissions at the relay (MAC channel) is shown to be optimal. We also show that if the two transmitters use identical lattices with minimum angle decoding, we can achieve the same rate of 1/2 log(0.5 + snr). The proposed scheme can be thought of as a joint physical layer, network layer code which outperforms other recently proposed analog network coding schemes.
Particle Filtering for Large Dimensional State Spaces with Multimodal Observation Likelihoods
Venue: arXiv cs.IT 2008
Year: 2008

We study efficient importance sampling techniques for particle filtering (PF) when either (a) the observation likelihood (OL) is frequently multimodal or heavy-tailed, or (b) the state space dimension is large or both. When the OL is multimodal, but the state transition pdf (STP) is narrow enough, the optimal importance density is usually unimodal. Under this assumption, many techniques have been proposed. But when the STP is broad, this assumption does not hold. We study how existing techniques can be generalized to situations where the optimal importance density is multimodal, but is unimodal conditioned on a part of the state vector. Sufficient conditions to test for the unimodality of this conditional posterior are derived. The number of particles, N, to accurately track using a PF increases with state space dimension, thus making any regular PF impractical for large dimensional tracking problems. We propose a solution that partially addresses this problem. An important class of large dimensional problems with multimodal OL is tracking spatially varying physical quantities such as temperature or pressure in a large area using a network of sensors which may be nonlinear and/or may have non-negligible failure probabilities.
On some entropy functionals derived from Rényi information divergence
Venue: arXiv cs.IT 2008
Year: 2008

We consider the maximum entropy problems associated with Rényi $Q$-entropy, subject to two kinds of constraints on expected values. The constraints considered are a constraint on the standard expectation, and a constraint on the generalized expectation as encountered in nonextensive statistics. The optimum maximum entropy probability distributions, which can exhibit a power-law behaviour, are derived and characterized. The Rényi entropy of the optimum distributions can be viewed as a function of the constraint. This defines two families of entropy functionals in the space of possible expected values. General properties of these functionals, including nonnegativity, minimum, convexity, are documented. Their relationships as well as numerical aspects are also discussed. Finally, we work out some specific cases for the reference measure $Q(x)$ and recover in a limit case some well-known entropies.
Diversity-Multiplexing Tradeoff in Selective-Fading Multiple-Access MIMO Channels
Venue: arXiv cs.IT 2008
Year: 2008

We establish the optimal diversity-multiplexing (DM) tradeoff of coherent selective-fading multiple-access multiple-input multiple-output (MIMO) channels and provide corresponding code design criteria. As a byproduct, on the conceptual level, we find an interesting relation between the DM tradeoff framework and the notion of dominant error event regions which was first introduced in the AWGN case by Gallager, IEEE Trans. IT, 1985. This relation allows to accurately characterize the error mechanisms in MIMO fading multiple-access channels. In particular, we find that, for a given rate tuple, the maximum achievable diversity order is determined by the error event that dominates the total error probability exponentially in SNR. Finally, we show that the distributed space-time code construction proposed recently by Badr and Belfiore, Int. Zurich Seminar on Commun., 2008, satisfies the code design criteria derived in this paper.
(m,k)-firm constraints and DBP scheduling: impact of the initial k-sequence and exact schedulability test
Venue: arXiv cs.OS 2008
Year: 2008

In this paper we study the scheduling of (m,k)-firm synchronous periodic task systems using the Distance Based Priority (DBP) scheduler. We first show three phenomena: (i) choosing, for each task, the initial k-sequence 1^k is not optimal, (ii) we can even start the scheduling from a (fictive) error state (in regard to the initial k-sequence) and (iii) the period of feasible DBP-schedules is not necessarily the task hyper-period. We then show that any feasible DBP-schedule is periodic and we upper-bound the length of that period. Lastly, based on our periodicity result we provide an exact schedulability test.
A Pseudo-Boolean Solution to the Maximum Quartet Consistency Problem
Venue: arXiv cs.AI 2008
Year: 2008

Determining the evolutionary history of a given biological data is an important task in biological sciences. Given a set of quartet topologies over a set of taxa, the Maximum Quartet Consistency (MQC) problem consists of computing a global phylogeny that satisfies the maximum number of quartets. A number of solutions have been proposed for the MQC problem, including Dynamic Programming, Constraint Programming, and more recently Answer Set Programming (ASP). ASP is currently the most efficient approach for optimally solving the MQC problem. This paper proposes encoding the MQC problem with pseudo-Boolean (PB) constraints. The use of PB allows solving the MQC problem with efficient PB solvers, and also allows considering different modeling approaches for the MQC problem. Initial results are promising, and suggest that PB can be an effective alternative for solving the MQC problem.
Asymptotically Good LDPC Convolutional Codes Based on Protographs
Venue: arXiv cs.IT 2008
Year: 2008

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. In this paper, asymptotic methods are used to calculate a lower bound on the free distance for several ensembles of asymptotically good protograph-based LDPC convolutional codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of corresponding LDPC block codes.
Iterative Hard Thresholding for Compressed Sensing
Venue: arXiv cs.IT 2008
Year: 2008

Compressed sensing is a technique to sample compressible signals below the Nyquist rate, whilst still allowing near optimal reconstruction of the signal. In this paper we present a theoretical analysis of the iterative hard thresholding algorithm when applied to the compressed sensing recovery problem. We show that the algorithm has the following properties (made more precise in the main text of the paper) - It gives near-optimal error guarantees. - It is robust to observation noise. - It succeeds with a minimum number of observations. - It can be used with any sampling operator for which the operator and its adjoint can be computed. - The memory requirement is linear in the problem size. - Its computational complexity per iteration is of the same order as the application of the measurement operator or its adjoint. - It requires a fixed number of iterations depending only on the logarithm of a form of signal to noise ratio of the signal. - Its performance guarantees are uniform in that they only depend on properties of the sampling operator and signal sparsity.
Infinity-Norm Sphere-Decoding
Venue: arXiv cs.IT 2008
Year: 2008

The most promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is the l-2 norm. It was, however, recently observed that using the l-infinity norm instead reduces the hardware complexity of SD considerably at only a marginal performance loss. These savings result from a reduction in the length of the critical path in the circuit and the silicon area required for metric computation, but are also, as observed previously through simulation results, a consequence of a reduction in the computational (i.e., algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis of l-infinity norm SD. For i.i.d. Rayleigh fading MIMO channels, we show that l-infinity norm SD achieves full diversity order with an asymptotic SNR gap, compared to l-2 norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity of l-infinity norm SD based on which we establish that its complexity scales exponentially in the system size. Finally, we characterize the tree pruning behavior of l-infinity norm SD and show that it behaves fundamentally different from that of l-2 norm SD.
Discrete Mathematics for Computer Science, Some Notes
Venue: arXiv cs.DM 2008
Year: 2008

These are notes on discrete mathematics for computer scientists. The presentation is somewhat unconventional. Indeed I begin with a discussion of the basic rules of mathematical reasoning and of the notion of proof formalized in a natural deduction system ``a la Prawitz''. The rest of the material is more or less traditional but I emphasize partial functions more than usual (after all, programs may not terminate for all input) and I provide a fairly complete account of the basic concepts of graph theory.
Sponsored Search Auctions with Markovian Users
Venue: arXiv cs.GT 2008
Year: 2008

Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. Currently, the most popular auction for sponsored search is the "Generalized Second Price" (GSP) auction in which advertisers are assigned to slots in the decreasing order of their "score," which is defined as the product of their bid and click-through rate. In the past few years, there has been significant research on the game-theoretic issues that arise in an advertiser's interaction with the mechanism as well as possible redesigns of the mechanism, but this ranking order has remained standard. From a search engine's perspective, the fundamental question is: what is the best assignment of advertisers to slots? Here "best" could mean "maximizing user satisfaction," "most efficient," "revenue-maximizing," "simplest to interact with," or a combination of these. To answer this question we need to understand the behavior of a search engine user when she sees the displayed ads, since that defines the commodity the advertisers are bidding on, and its value. Most prior work has assumed that the probability of a user clicking on an ad is independent of the other ads shown on the page. We propose a simple Markovian user model that does not make this assumption. We then present an algorithm to determine the most efficient assignment under this model, which turns out to be different than that of GSP. A truthful auction then follows from an application of the Vickrey-Clarke-Groves (VCG) mechanism. Further, we show that our assignment has many of the desirable properties of GSP that makes bidding intuitive. At the technical core of our result are a number of insights about the structure of the optimal assignment.
Linear and Non Linear Behaviour of Mechanical Resonators for Optimized Inertial Electromagnetic Microgenerators
Venue: arXiv cs.OH 2008
Year: 2008

The need for wearable or abandoned microsystems, as well as the trend to a lower power consumption of electronic devices, make miniaturized renewable energy generators a viable alternative to batteries. Among the different alternatives, an interesting option is the use of inertial microgenerators for energy scavenging from vibrations present in the environment. These devices constitute perpetual energy sources without the need for refilling, thus being well suited for abandoned sensors, wireless systems or microsystems which must be embedded within the structure, without outside physical connections. Different electromagnetic energy scavenging devices have been described in the literature [1,2,3], based on the use of a velocity damped resonator, which is well suited for harvesting of vibrational energy induced by the operation of machines. These vibrations are characterized by a well defined frequency (in the range between few Hz's and few kHz's) and low displacement amplitudes. Adjusting the resonant frequency of the system to that of the vibrations allows amplification of these low amplitude displacements. Moreover, for these applications, the use of an electromagnetic device has the potential advantages of a good level of compatibility with Si Microsystem technology, as well as the possibility of relatively high electromechanical coupling with simple designs.
Processing and Characterization of Precision Microparts from Nickel-based Materials
Venue: arXiv cs.OH 2008
Year: 2008

The objective of this research was to study the influence of electroplating parameters on electrodeposit characteristics for the production of nickel (Ni) and nickel-iron (Ni-Fe) microparts by photoelectroforming. The research focused on the most relevant parameter for industry, which is the current density, because it determines the process time and the consumed energy. The results of the Ni and Ni-Fe characterisations can be divided into two aspects closely linked with each other ; the morphology and the hardness.
Top-Down Behavioral Modeling Methodology of a Piezoelectric Microgenerator For Integrated Power Harvesting Systems
Venue: arXiv cs.OH 2008
Year: 2008

In this study, we developed a top/down methodology for behavioral and structural modeling of multi-domain microsystems. Then, we validated this methodology through a study case : a piezoelectric microgenerator. We also proved the effectiveness of VHDL-AMS language not only for modeling in behavioral and structural levels but also in writing physical models that can predict the experimental results. Finally, we validated these models by presenting and discussing simulations results.
Hybridization of Magnetism and Piezoelectricity for an Energy Scavenger based on Temporal Variation of Temperature
Venue: arXiv cs.OH 2008
Year: 2008

Autonomous microsystems are confronted today to a major challenge : the one of energy supply. Energy scavenging, i.e. collecting energy from the ambient environment has been developed to answer this problematic. Various sources have already been successfully used (solar, vibration). This article presents temporal variations of temperature as a new source of exploitable energy. A brief review will take place at the beginning, exposing the different approaches used in the past. Then we will focus our attention on hybridization of magnetism and piezoelectricity. A new kind of thermal generator is proposed and a preliminary model is exposed. Conclusions will be drawn on the suitability of this prototype and the improvements that are needed to increase its potential.
Cell Trapping Utilizing Insulator-based Dielectrophoresis in The Open-Top Microchannels
Venue: arXiv cs.OH 2008
Year: 2008

The ability to manipulate or separate a biological small particle, such as a living cell and embryo, is fundamental needed to many biological and medical applications. The insulator-based dielectrophoresis (iDEP) trapping is composed of conductless tetragon structures in micro-chip. In this study, a lower conductive material of photoresist was adopted as a structure in open-top microchannel instead of a metallic wire to squeeze the electric field in a conducting solution, therefore, creating a high field gradient with a local maximum. The microchip with the open-top microchannels was designed and fabricated herein. The insulator-based DEP trapping microchip with the open-top microchannels was designed and fabricated in this work. The cells trapped by DEP force could be further treated or cultured in the open-top microchannel ; however, those trapped in the microchip with enclosed microchannels could not be proceeded easily.
New high fill-factor triangular micro-lens array fabrication method using UV proximity printing
Venue: arXiv cs.OH 2008
Year: 2008

A simple and effective method to fabricate a high fill-factor triangular microlens array using the proximity printing in lithography process is reported. The technology utilizes the UV proximity printing by controlling a printing gap between the mask and substrate. The designed approximate triangle microlens array pattern can be fabricated the high fill-factor triangular microlens array in photoresist. It is due to the UV light diffraction to deflect away from the aperture edges and produce a certain exposure in photoresist material outside the aperture edges. This method can precisely control the geometric profile of high fill factor triangular microlens array. The experimental results showed that the triangular micro-lens array in photoresist could be formed automatically when the printing gap ranged from 240 micrometers to 840 micrometers. The gapless triangular microlens array will be used to increases of luminance for backlight module of liquid crystal displays.
High Density Through Silicon Via (TSV)
Venue: arXiv cs.OH 2008
Year: 2008

The Through Silicon Via (TSV) process developed by Silex provides down to 30 micrometers pitch for through wafer connections in up to 600 micrometers thick substrates. Integrated with MEMS designs it enables significantly reduced die size and true "Wafer Level Packaging" - features that are particularly important in consumer market applications. The TSV technology also enables integration of advanced interconnect functions in optical MEMS, sensors and microfluidic devices. In addition the Via technology opens for very interesting possibilities considering integration with CMOS processing. With several companies using the process already today, qualified volume manufacturing in place and a line-up of potential users, the process is becoming a standard in the MEMS industry. We provide a introduction to the via formation process and also present some on the novel solutions made available by the technology.
Noise Analysis and Noise-based Optimization for Resonant MEMS Structures
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents a detailed noise analysis and a noise-based optimization procedure for resonant MEMS structures. A design for high sensitivity of MEMS structures needs to take into account the noise shaping induced by damping phenomena at micro scale. The existing literature presents detailed models for the damping at microscale, but usually neglects them in the noise analysis process, assuming instead a white spectrum approximation for the mechano-thermal noise. The present work extends the implications of the complex gas-solid interaction into the field of noise analysis for mechanical sensors, and provides a semi-automatic procedure for behavioral macromodel extraction and sensor optimization with respect to signal-to-noise ratio.
Design and Fabrication of Acoustic Wave Actuated Microgenerator for Portable Electronic Devices
Venue: arXiv cs.OH 2008
Year: 2008

The past few years have seen an increasing focus on energy harvesting issue, including power supply for portable electric devices. Utilize scavenging ambient energy from the environment could eliminate the need for batteries and increase portable device lifetimes indefinitely. In addition, through MEMS technology fabricated micro-generator could easy integrate with these small or portable devices. Several different ambient sources, including solar, vibration and temperature effect, have already exploited [1-3]. Each energy source should be used in suitable environment, therefore to produce maximum efficiency. In this paper, we present an acoustic wave actuated micro-generator for power system by using the energy of acoustic waves, such as the sound from human voices or speakerphone, to actuate a MEMS-type electromagnetic transducer. This provides a longer device lifetime and greater power system convenience. Moreover, it is convenient to integrate MEMS-based microgenerators with small or porta le devices
Contact state analysis using NFIS and SOM
Venue: arXiv cs.NE 2008
Year: 2008

This paper reports application of neuro- fuzzy inference system (NFIS) and self organizing feature map neural networks (SOM) on detection of contact state in a block system. In this manner, on a simple system, the evolution of contact states, by parallelization of DDA, has been investigated. So, a comparison between NFIS and SOM results has been presented. The results show applicability of the proposed methods, by different accuracy, on detection of contact's distribution.
Scaling Laws for Overlaid Wireless Networks: A Cognitive Radio Network vs. a Primary Network
Venue: arXiv cs.IT 2008
Year: 2008

We study the scaling laws for the throughputs and delays of two coexisting wireless networks that operate in the same geographic region. The primary network consists of Poisson distributed legacy users of density n, and the secondary network consists of Poisson distributed cognitive users of density m, with m>n. The primary users have a higher priority to access the spectrum without particular considerations for the secondary users, while the secondary users have to act conservatively in order to limit the interference to the primary users. With a practical assumption that the secondary users only know the locations of the primary transmitters (not the primary receivers), we first show that both networks can achieve the same throughput scaling law as what Gupta and Kumar [1] established for a stand-alone wireless network if proper transmission schemes are deployed, where a certain throughput is achievable for each individual secondary user (i.e., zero outage) with high probability. By using a fluid model, we also show that both networks can achieve the same delay-throughput tradeoff as the optimal one established by El Gamal et al. [2] for a stand-alone wireless network.