Theory and Algorithms Commons^™

Identifying High-Dimension Subspace Subcodes Of Reed-Solomon Codes, Sarah Adams

Sarah Spence Adams

Subspace subcodes of Reed-Solomon (SSRS) codes were introduced by Hattori, McEliece, Solomo, and Lin in the mid-1990s. These authors found a complicated dimension formula and a simple, tight lower bound on thedimension of SSRS codes over F₂^m. We prove a conjecture of Hattori concerning how to identify subspaces that can be used to build SSRS codes whose dimension exceeds this lower bound.

The Minimum Decoding Delay Of Maximum Rate Complex Orthogonal Space–Time Block Codes, Sarah Adams, Nathaniel Karst, Jonathan Pollack

Sarah Spence Adams

The growing demand for efficient wireless transmissions over fading channels motivated the development ofspace-time block codes. Space-time block codes built from generalized complex orthogonal designs are particularly attractive because the orthogonality permits a simple decoupled maximum-likelihood decodingalgorithm while achieving full transmit diversity. The two main research problems for these complex orthogonalspace-time block codes (COSTBCs) have been to determine for any number of antennas the maximum rate andthe minimum decoding delay for a maximum rate code. The maximum rate for COSTBCs was determined by Liang in 2003. This paper addresses the second fundamental problem by providing a tight lower bound on …

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …

On The Issue Of Decoupled Decoding Of Codes Derived From Quaternion Orthogonal Designs, Tadeusz Wysocki, Beata Wysocki, Sarah Spence Adams

Sarah Spence Adams

Quaternion orthogonal designs (QODs) have been previously introduced as a basis for orthogonal space-time polarization block codes (OSTPBCs). This note will serve to correct statements concerning the optimality of a decoupled maximum-likelihood (ML) decoding algorithm. It will be shown that when compared to coupled decoding, the decoupled decoding is only optimal in certain cases. This raises several open problems concerning the decoding of OSTPBCs.

A Parameterized Stereo Vision Core For Fpgas, Mark Chang, Stephen Longfield

Mark L. Chang

We present a parameterized stereo vision core suitable for a wide range of FPGA targets and stereo vision applications. By enabling easy tuning of algorithm parameters, our system allows for rapid exploration of the design space and simpler implementation of high-performance stereo vision systems. This implementation utilizes the census transform algorithm to calculate depth information from a pair of images delivered from a simulated stereo camera pair. This work advances our previous work through implementation improvements, a stereo camera pair simulation framework, and a scalable stereo vision core.

Precis: A Design-Time Precision Analysis Tool, Mark L. Chang, Scott Hauck

Mark L. Chang

Currently, few tools exist to aid the FPGA developer in translating an algorithm designed for a general-purpose-processor into one that is precision-optimized for FPGAs. This task requires extensive knowledge of both the algorithm and the target hardware. We present a design-time tool, Precis, which assists the developer in analyzing the precision requirements of algorithms specified in MATLAB. Through the combined use of simulation, user input, and program analysis, we demonstrate a methodology for precision analysis that can aid the developer in focusing their manual precision optimization efforts.

Precis: A Usercentric Word-Length Optimization Tool, Mark Chang, Scott Hauck

Mark L. Chang

Translating an algorithm designed for a general-purpose processor into an algorithm optimized for custom logic requires extensive knowledge of the algorithm and the target hardware. Precis lets designers analyze the precision requirements of algorithms specified in Matlab. The design time tool combines simulation, user input, and program analysis to help designers focus their manual precision optimization efforts.

Low-Cost Stereo Vision On An Fpga, Chris A. Murphy, Daniel Lindquist, Ann Marie Rynning, Thomas Cecil, Sarah Leavitt, Mark L. Chang

Mark L. Chang

We present a low-cost stereo vision implementation suitable for use in autonomous vehicle applications and designed with agricultural applications in mind. This implementation utilizes the Census transform algorithm to calculate depth maps from a stereo pair of automotive-grade CMOS cameras. The final prototype utilizes commodity hardware, including a Xilinx Spartan-3 FPGA, to process 320times240 pixel images at greater than 150 frames per second and deliver them via a USB 2.0 interface.

Interactionless Calendar-Based Training For 802.11 Localization, Mark Chang, Andrew J. Barry, Noah L. Tye

Mark L. Chang

This paper presents our work in solving one of the weakest links in 802.11-based indoor-localization: the training of ground-truth received signal strength data. While crowdsourcing this information has been demonstrated to be a viable alternative to the time consuming and accuracy-limited process of manual training, one of the chief drawbacks is the rate at which a system can be trained. We demonstrate an approach that utilizes users' calendar and appointment information to perform interactionless training of an 802.11-based indoor localization system. Our system automatically determines if a user attended a calendar event, resulting in accuracy comparable to our previously published …

Targeted Maximum Likelihood Estimation For Dynamic Treatment Regimes In Sequential Randomized Controlled Trials, Paul Chaffee, Mark J. Van Der Laan

Paul H. Chaffee

Sequential Randomized Controlled Trials (SRCTs) are rapidly becoming essential tools in the search for optimized treatment regimes in ongoing treatment settings. Analyzing data for multiple time-point treatments with a view toward optimal treatment regimes is of interest in many types of afflictions: HIV infection, Attention Deficit Hyperactivity Disorder in children, leukemia, prostate cancer, renal failure, and many others. Methods for analyzing data from SRCTs exist but they are either inefficient or suffer from the drawbacks of estimating equation methodology. We describe an estimation procedure, targeted maximum likelihood estimation (TMLE), which has been fully developed and implemented in point treatment settings, …

Computing Highly Accurate Or Exact P-Values Using Importance Sampling, Chris Lloyd

Chris J. Lloyd

Especially for discrete data, standard first order P-values can suffer from poor accuracy, even for quite large sample sizes. Moreover, different test statistics can give practically different results. There are several approaches to computing P-values which do not suffer these defects, such as parametric bootstrap P-values or the partially maximised P-values of Berger and Boos (1994).

Both these methods require computing the exact tail probability of the approximate P-value as a function of the nuisance parameter/s, known as the significance profile. For most practical problems, this is not computationally feasible. I develop an importance sampling approach to this problem. A …

Multi-Tier Exploration Concept Demonstration Mission, Jeremy Straub

Jeremy Straub

A multi-tier, multi-craft mission architecture has been proposed but, despite its apparent promise, limited use and testing of the architecture has been conducted. This paper proposes and details a mission concept and its implementation for testing this architecture in the terrestrial environment. It is expected that this testing will allow significant refinement of the proposed architecture as well as providing data on its suitability for use in both terrestrial and extra-terrestrial applications. Logistical and technical challenges with this testing are discussed.

The Discrete Yang-Fourier Transforms In Fractal Space, Yang Xiao-Jun

Xiao-Jun Yang

The Yang-Fourier transform (YFT) in fractal space is a generation of Fourier transform based on the local fractional calculus. The discrete Yang-Fourier transform (DYFT) is a specific kind of the approximation of discrete transform, used in Yang-Fourier transform in fractal space. This paper points out new standard forms of discrete Yang-Fourier transforms (DYFT) of fractal signals, and both properties and theorems are investigated in detail.

Expression Of Generalized Newton Iteration Method Via Generalized Local Fractional Taylor Series, Yang Xiao-Jun

Xiao-Jun Yang

Local fractional derivative and integrals are revealed as one of useful tools to deal with everywhere continuous but nowhere differentiable functions in fractal areas ranging from fundamental science to engineering. In this paper, a generalized Newton iteration method derived from the generalized local fractional Taylor series with the local fractional derivatives is reviewed. Operators on real line numbers on a fractal space are induced from Cantor set to fractional set. Existence for a generalized fixed point on generalized metric spaces may take place.

Imagining Emergent Metadata, Realizing The Emergent Web, Jason A. Bengtson

Jason A Bengtson

Current metadata schemas are largely analog technology grafted onto the digital format. They have three inherent limitations that need to be transcended: they generate a static product which must be changed manually, they revolve around the needs of human, rather than mechanistic agents, and they are limited by the imagination and organizational capabilities of human agency. The author argues that to meet future challenges metadata will have to take a more flexible, adaptive form that centers on the needs of the machine in searching, interpretation and organization until the information it proxies enters into the human sphere. The author further …

The Art Of Redirection: Putting Mobile Devices Where You Want Them, Jason A. Bengtson

Jason A Bengtson

Mobile technology has exploded, with many libraries experiencing a surge in access to their resources through mobile devices. In response, many institutions have created or are creating mobile sites designed to accommodate themselves to the unique strictures of these devices. One hurdle faced by these organizations, however, is getting mobile users to those sites. One solution is mobile redirect scripts, which automatically redirect mobile users from a regular page to a mobile page. These scripts come in various forms and present unique challenges to libraries. How are these scripts created? What triggers can or should be used to activate them? …

Imagining Emergent Metadata, Realizing The Emergent Web, Jason A. Bengtson

Jason A Bengtson

Current metadata schemas are largely analog technology grafted onto the digital format. They have three inherent limitations that need to be transcended: they generate a static product which must be changed manually, they revolve around the needs of human, rather than mechanistic agents, and they are limited by the imagination and organizational capabilities of human agency. The author argues that to meet future challenges metadata will have to take a more flexible, adaptive form that centers on the needs of the machine in searching, interpretation and organization until the information it proxies enters into the human sphere. The author further …

The Zero-Mass Renormalization Group Differential Equations And Limit Cycles In Non-Smooth Initial Value Problems, Yang Xiaojun

Xiao-Jun Yang

In the present paper, using the equation transform in fractal space, we point out the zero-mass renormalization group equations. Under limit cycles in the non-smooth initial value, we devote to the analytical technique of the local fractional Fourier series for treating zero-mass renormalization group equations, and investigate local fractional Fourier series solutions.

Shortest Geometric Paths Analysis In Structural Biology, Ryan G. Coleman

Ryan G Coleman

The surface of a macromolecule, such as a protein, represents the contact point of any interaction that molecule has with solvent, ions, small molecules or other macromolecules. Analyzing the surface of macromolecules has a rich history but analyzing the distances from this surface to other surfaces or volumes has not been extensively explored. Many important questions can be answered quantitatively through these analyses. These include: what is the depth of a pocket or groove on the surface? what is the overall depth of the protein? how deeply are atoms buried from the surface? where are the tunnels in a protein? …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …

A Novel Approach To Processing Fractal Dynamical Systems Using The Yang-Fourier Transforms, Yang Xiaojun

Xiao-Jun Yang

In the present paper, local fractional continuous non-differentiable functions in fractal space are investigated, and the control method for processing dynamic systems in fractal space are proposed using the Yang-Fourier transform based on the local fractional calculus. Two illustrative paradigms for control problems in fractal space are given to elaborate the accuracy and reliable results.

Theory And Applications Of Local Fractional Fourier Analysis, Yang Xiaojun

Xiao-Jun Yang

Local fractional Fourier analysis is a generalized Fourier analysis in fractal space. The local fractional calculus is one of useful tools to process the local fractional continuously non-differentiable functions (fractal functions). Based on the local fractional derivative and integration, the present work is devoted to the theory and applications of local fractional Fourier analysis in generalized Hilbert space. We investigate the local fractional Fourier series, the Yang-Fourier transform, the generalized Yang-Fourier transform, the discrete Yang-Fourier transform and fast Yang-Fourier transform.

Heat Transfer In Discontinuous Media, Yang Xiaojun

Xiao-Jun Yang

From the fractal geometry point of view, the interpretations of local fractional derivative and local fractional integration are pointed out in this paper. It is devoted to heat transfer in discontinuous media derived from local fractional derivative. We investigate the Fourier law and heat conduction equation (also local fractional instantaneous heat conduct equation) in fractal orthogonal system based on cantor set, and extent them. These fractional differential equations are described in local fractional derivative sense. The results are efficiently developed in discontinuous media.

A Short Note On Local Fractional Calculus Of Function Of One Variable, Yang Xiaojun

Xiao-Jun Yang

Local fractional calculus (LFC) handles everywhere continuous but nowhere differentiable functions in fractal space. This note investigates the theory of local fractional derivative and integral of function of one variable. We first introduce the theory of local fractional continuity of function and history of local fractional calculus. We then consider the basic theory of local fractional derivative and integral, containing the local fractional Rolle’s theorem, L’Hospital’s rule, mean value theorem, anti-differentiation and related theorems, integration by parts and Taylor’ theorem. Finally, we study the efficient application of local fractional derivative to local fractional extreme value of non-differentiable functions, and give …

A New Successive Approximation To Non-Homogeneous Local Fractional Volterra Equation, Yang Xiaojun

Xiao-Jun Yang

A new successive approximation approach to the non-homogeneous local fractional Valterra equation derived from local fractional calculus is proposed in this paper. The Valterra equation is described in local fractional integral operator. The theory of local fractional derivative and integration is one of useful tools to handle the fractal and continuously non-differentiable functions, was successfully applied in engineering problem. We investigate an efficient example of handling a non-homogeneous local fractional Valterra equation.

Advanced Local Fractional Calculus And Its Applications, Yang Xiaojun

Xiao-Jun Yang

This book is the first international book to study theory and applications of local fractional calculus (LFC). It is an invitation both to the interested scientists and the engineers. It presents a thorough introduction to the recent results of local fractional calculus. It is also devoted to the application of advanced local fractional calculus on the mathematics science and engineering problems. The author focuses on multivariable local fractional calculus providing the general framework. It leads to new challenging insights and surprising correlations between fractal and fractional calculus. Keywords: Fractals - Mathematical complexity book - Local fractional calculus- Local fractional partial …

A Short Introduction To Yang-Laplace Transforms In Fractal Space, Yang Xiaojun

Xiao-Jun Yang

The Yang-Laplace transforms [W. P. Zhong, F. Gao, In: Proc. of the 2011 3rd International Conference on Computer Technology and Development, 209-213, ASME, 2011] in fractal space is a generalization of Laplace transforms derived from the local fractional calculus. This letter presents a short introduction to Yang-Laplace transforms in fractal space. At first, we present the theory of local fractional derivative and integral of non-differential functions defined on cantor set. Then the properties and theorems for Yang-Laplace transforms are tabled, and both the initial value theorem and the final value theorem are investigated. Finally, some applications to the wave equation …

Local Fractional Integral Equations And Their Applications, Yang Xiaojun

Xiao-Jun Yang

This letter outlines the local fractional integral equations carried out by the local fractional calculus (LFC). We first introduce the local fractional calculus and its fractal geometrical explanation. We then investigate the local fractional Volterra/ Fredholm integral equations, local fractional nonlinear integral equations, local fractional singular integral equations and local fractional integro-differential equations. Finally, their applications of some integral equations to handle some differential equations with local fractional derivative and local fractional integral transforms in fractal space are discussed in detail.