Multiresolution Area-based Fractal Dimension Estimation of Signals Applied to EEG Data

In this paper, we present an approach to estimate fractal complexity of discrete time signal waveforms based on computation of area bounded by sample points of the signal at different time resolutions. The slope of best straight line fit to the graph of log(A(rk)A / rk(2)) versus log(l/rk) is estimated, where A(rk) is the area computed at different time resolutions and rk time resolutions at which the area have been computed. The slope quantifies complexity of the signal and it is taken as an estimate of the fractal dimension (FD). The proposed approach is used to estimate the fractal dimension of parametric fractal signals with known fractal dimensions and the method has given accurate results. The estimation accuracy of the method is compared with that of Higuchi's and Sevcik's methods. The proposed method has given more accurate results when compared with that of Sevcik's method and the results are comparable to that of the Higuchi's method. The practical application of the complexity measure in detecting change in complexity of signals is discussed using real sleep electroencephalogram recordings from eight different subjects. The FD-based approach has shown good performance in discriminating different stages of sleep.

Signal Characterization using Fractal Dimension

Fractal Dimensions (FD) are popular metrics for characterizing signals. They are used as complexity measuresin signal analysis applications in various fields. However, proper interpretation of such analyses has not been thoroughly addressed. In this paper, we study the effect of various signal properties on FD and interpret results in terms of classical signal processing concepts such as amplitude, frequency,number of harmonics, noise power and signal bandwidth. We have used Higuchi’s method for estimating FDs. This study helps in gaining a better understanding of the FD complexity measure for various signal parameters. Our results indicate that FD is a useful metric in estimating various signal properties. As an application of the FD measure in real world scenario, the FD is used as a feature in discriminating seizures from seizure free intervals in intracranial EEG data recordings and the FD feature has given good discrimination performance.

Complexity analysis of EEG in patients with schizophrenia using fractal dimension

We computed Higuchi's fractal dimension (FD) of resting, eyes closed EEG recorded from 30 scalp locations in 18 male neuroleptic-naive, recent-onset schizophrenia (NRS) subjects and 15 male healthy control (HC) subjects, who were group-matched for age. Schizophrenia patients showed a diffuse reduction of FD except in the bilateral temporal and occipital regions, with the reduction being most prominent bifrontally. The positive symptom (PS) schizophrenia subjects showed FD values similar to or even higher than HC in the bilateral temporo-occipital regions, along with a co-existent bifrontal FD reduction as noted in the overall sample of NRS. In contrast, this increase in FD values in the bilateral temporo-occipital region was absent in the negative symptom (NS) subgroup. The regional differences in complexity suggested by these findings may reflect the aberrant brain dynamics underlying the pathophysiology of schizophrenia and its symptom dimensions. Higuchi's method of measuring FD directly in the time domain provides an alternative for the more computationally intensive nonlinear methods of estimating EEG complexity.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Nonadiabatic charge pumping by oscillating potentials in one dimension: Results for infinite system and finite ring

We study charge pumping when a combination of static potentials and potentials oscillating with a time period T is applied in a one-dimensional system of noninteracting electrons. We consider both an infinite system using the Dirac equation in the continuum approximation and a periodic ring with a finite number of sites using the tight-binding model. The infinite system is taken to be coupled to reservoirs on the two sides which are at the same chemical potential and temperature. We consider a model in which oscillating potentials help the electrons to access a transmission resonance produced by the static potentials and show that nonadiabatic pumping violates the simple sin phi rule which is obeyed by adiabatic two-site pumping. For the ring, we do not introduce any reservoirs, and we present a method for calculating the current averaged over an infinite time using the time evolution operator U(T) assuming a purely Hamiltonian evolution. We analytically show that the averaged current is zero if the Hamiltonian is real and time-reversal invariant. Numerical studies indicate another interesting result, namely, that the integrated current is zero for any time dependence of the potential if it is applied to only one site. Finally we study the effects of pumping at two sites on a ring at resonant and nonresonant frequencies, and show that the pumped current has different dependences on the pumping amplitude in the two cases.

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

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), 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-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), 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-epsilon)) for any epsilon > 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-epsilon)) for any epsilon > 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. (C) 2010 Elsevier B.V. All rights reserved.

Spin-1 Kitaev model in one dimension

We study a one-dimensional version of the Kitaev model on a ring of size N, in which there is a spin S > 1/2 on each site and the Hamiltonian is J Sigma(nSnSn+1y)-S-x. The cases where S is integer and half-odd integer are qualitatively different. We show that there is a Z(2)-valued conserved quantity W-n for each bond (n, n + 1) of the system. For integer S, the Hilbert space can be decomposed into 2N sectors, of unequal sizes. The number of states in most of the sectors grows as d(N), where d depends on the sector. The largest sector contains the ground state, and for this sector, for S=1, d=(root 5+1)/2. We carry out exact diagonalization for small systems. The extrapolation of our results to large N indicates that the energy gap remains finite in this limit. In the ground-state sector, the system can be mapped to a spin-1/2 model. We develop variational wave functions to study the lowest energy states in the ground state and other sectors. The first excited state of the system is the lowest energy state of a different sector and we estimate its excitation energy. We consider a more general Hamiltonian, adding a term lambda Sigma W-n(n), and show that this has gapless excitations in the range lambda(c)(1)<=lambda <=lambda(c)(2). We use the variational wave functions to study how the ground-state energy and the defect density vary near the two critical points lambda(c)(1) and lambda(c)(2).

Signal characterization using fractal dimension

Fractal Dimensions (FD) are one of the popular measures used for characterizing signals. They have been used as complexity measures of signals in various fields including speech and biomedical applications. However, proper interpretation of such analyses has not been thoroughly addressed. In this paper, we study the effect of various signal properties on FD and interpret results in terms of classical signal processing concepts such as amplitude, frequency, number of harmonics, noise power and signal bandwidth. We have used Higuchi's method for estimating FDs. This study may help in gaining a better understanding of the FD complexity measure itself, and for interpreting changing structural complexity of signals in terms of FD. Our results indicate that FD is a useful measure in quantifying structural changes in signal properties.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Use of running fractal dimension for the analysis of changing patterns in electroencephalograms

Running fractal dimensions were measured on four channels of an electroencephalogram (EEG) recorded from a normal volunteer. The changes in the background activity due to eye closure were clearly differentiated by the fractal method. The compressed spectral array (CSA) and the running fractal dimensions of the EEG showed corresponding changes with respect to change in the background activity. The fractal method was also successful in detecting low amplitude spikes and the changes in the patterns in the EEG. The effects of different window lengths and shifts on the running fractal dimension have also been studied. The utility of fractal method for EEG data compression is highlighted.

Computing Fractal Dimension of Signals using Multiresolution Box-counting Method

In this paper, we have developed a method to compute fractal dimension (FD) of discrete time signals, in the time domain, by modifying the box-counting method. The size of the box is dependent on the sampling frequency of the signal. The number of boxes required to completely cover the signal are obtained at multiple time resolutions. The time resolutions are made coarse by decimating the signal. The loglog plot of total number of boxes required to cover the curve versus size of the box used appears to be a straight line, whose slope is taken as an estimate of FD of the signal. The results are provided to demonstrate the performance of the proposed method using parametric fractal signals. The estimation accuracy of the method is compared with that of Katz, Sevcik, and Higuchi methods. In ddition, some properties of the FD are discussed.

A New Class of Exactly Solvable Interacting Fermion Models in One Dimension

We investigate a model containing two species of one-dimensional fermions interacting via a gauge field determined by the positions of all particles of the opposite species. The model can be salved exactly via a simple unitary transformation. Nevertheless, correlation functions exhibit nontrivial interaction-dependent exponents. A similar model defined on a lattice is introduced and solved. Various generalizations, e.g., to the case of internal symmetries of the fermions, are discussed. The present treatment also clarifies certain aspects of Luttinger's original solution of the "Luttinger model."

Post-seizure EEG fractal dimension of first ECT predicts antidepressant response at two weeks

Background: Duration of seizure by itself is an insufficient criterion for a therapeutically adequate seizure in ECT. Therefore, measures of seizure EEG other than its duration need to be explored as indices of seizure adequacy and predictors of treatment response. We measured the EEG seizure using a geometrical method-fractal dimension (FD) and examined if this measure predicted remission. Methods: Data from an efficacy study on melancholic depressives (n = 40) is used for the present exploration. They received thrice or once weekly ECTs, each schedule at two energy levels - high or low energy level. FD was computed for early-, mid- and post-seizure phases of the ictal EEG. Average of the two channels was used for analysis. Results: Two-thirds of the patients (n = 25) were remitted at the end of 2 weeks. As expected, a significantly higher proportion of patients receiving thrice weekly ECT remitted than in patients receiving once weekly ECT. Smaller post-seizure FD at first ECT is the only variable which predicted remission status after six ECTs. within the once weekly ECT group too, smaller post-seizure FD was associated with remission status. Conclusions: Post-seizure FD is proposed as a novel measure of seizure adequacy and predictor of treatment response. Clinical implications: Seizure measures at first ECT may guide selection of ECT schedule to optimize ECT. Limitations: The study examined short term antidepressant effects only. The results may not be generalized to medication-resistant depressives. (C) 1999 Elsevier Science B.V. All rights reserved.