Reconstruction from incomplete data in cone-beam tomography

A method for reconstruction of an object f(x) x=(x,y,z) from a limited set of cone-beam projection data has been developed. This method uses a modified form of convolution back-projection and projection onto convex sets (POCS) for handling the limited (or incomplete) data problem. In cone-beam tomography, one needs to have a complete geometry to completely reconstruct the original three-dimensional object. While complete geometries do exist, they are of little use in practical implementations. The most common trajectory used in practical scanners is circular, which is incomplete. It is, however, possible to recover some of the information of the original signal f(x) based on a priori knowledge of the nature of f(x). If this knowledge can be posed in a convex set framework, then POCS can be utilized. In this report, we utilize this a priori knowledge as convex set constraints to reconstruct f(x) using POCS. While we demonstrate the effectiveness of our algorithm for circular trajectories, it is essentially geometry independent and will be useful in any limited-view cone-beam reconstruction.

Minimization Problems Based on Relative alpha-Entropy I: Forward Projection

Minimization problems with respect to a one-parameter family of generalized relative entropies are studied. These relative entropies, which we term relative alpha-entropies (denoted I-alpha), arise as redundancies under mismatched compression when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative alpha-entropies behave like squared Euclidean distance and satisfy the Pythagorean property. Minimizers of these relative alpha-entropies on closed and convex sets are shown to exist. Such minimizations generalize the maximum Renyi or Tsallis entropy principle. The minimizing probability distribution (termed forward I-alpha-projection) for a linear family is shown to obey a power-law. Other results in connection with statistical inference, namely subspace transitivity and iterated projections, are also established. In a companion paper, a related minimization problem of interest in robust statistics that leads to a reverse I-alpha-projection is studied.

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

Reliable Means of Diagnosis and Serovar Determination of Blood-Borne Salmonella Strains: Quick PCR Amplification of Unique Genomic Loci by Novel Primer Sets

Typhoid fever is becoming an ever increasing threat in the developing countries. We have improved considerably upon the existing PCR-based diagnosis method by designing primers against a region that is unique to Salmonella enterica subsp. enterica serovar Typhi and Salmonella enterica subsp. enterica serovar Paratyphi A, corresponding to the STY0312 gene in S. Typhi and its homolog SPA2476 in S. Paratyphi A. An additional set of primers amplify another region in S. Typhi CT18 and S. Typhi Ty2 corresponding to the region between genes STY0313 to STY0316 but which is absent in S. Paratyphi A. The possibility of a false-negative result arising due to mutation in hypervariable genes has been reduced by targeting a gene unique to typhoidal Salmonella serovars as a diagnostic marker. The amplified region has been tested for genomic stability by amplifying the region from clinical isolates of patients from various geographical locations in India, thereby showing that this region is potentially stable. These set of primers can also differentiate between S. Typhi CT18, S. Typhi Ty2, and S. Paratyphi A, which have stable deletions in this specific locus. The PCR assay designed in this study has a sensitivity of 95% compared to the Widal test which has a sensitivity of only 63%. As observed, in certain cases, the PCR assay was more sensitive than the blood culture test was, as the PCR-based detection could also detect dead bacteria.

A Branch and Bound Algorithm for a Transportation Type Problem with Piecewise Linear Convex Objective Function

A branch and bound type algorithm is presented in this paper to the problem of finding a transportation schedule which minimises the total transportation cost, where the transportation cost over each route is assumed to be a piecewice linear continuous convex function with increasing slopes. The algorithm is an extension of the work done by Balachandran and Perry, in which the transportation cost over each route is assumed to beapiecewise linear discontinuous function with decreasing slopes. A numerical example is solved illustrating the algorithm.

Non-linear Transceiver Designs with Imperfect CSIT Using Convex Optimization

In this paper, we consider non-linear transceiver designs for multiuser multi-input multi-output (MIMO) down-link in the presence of imperfections in the channel state information at the transmitter (CSIT). The base station (BS) is equipped with multiple transmit antennas and each user terminal is equipped with multiple receive antennas. The BS employs Tomlinson-Harashima precoding (THP) for inter-user interference pre-cancellation at the transmitter. We investigate robust THP transceiver designs based on the minimization of BS transmit power with mean square error (MSE) constraints, and balancing of MSE among users with a constraint on the total BS transmit power. We show that these design problems can be solved by iterative algorithms, wherein each iteration involves a pair of convex optimization problems. The robustness of the proposed algorithms to imperfections in CSIT is illustrated through simulations.

Conservation law with the flux function discontinuous in the space variable- II - Convex-concave type fluxes and generalized entropy solutions

We deal with a single conservation law with discontinuous convex-concave type fluxes which arise while considering sign changing flux coefficients. The main difficulty is that a weak solution may not exist as the Rankine-Hugoniot condition at the interface may not be satisfied for certain choice of the initial data. We develop the concept of generalized entropy solutions for such equations by replacing the Rankine-Hugoniot condition by a generalized Rankine-Hugoniot condition. The uniqueness of solutions is shown by proving that the generalized entropy solutions form a contractive semi-group in L-1. Existence follows by showing that a Godunov type finite difference scheme converges to the generalized entropy solution. The scheme is based on solutions of the associated Riemann problem and is neither consistent nor conservative. The analysis developed here enables to treat the cases of fluxes having at most one extrema in the domain of definition completely. Numerical results reporting the performance of the scheme are presented. (C) 2006 Elsevier B.V. All rights reserved.

Coding for Two-User Gaussian MAC with PSK and PAM Signal Sets

Constellation Constrained (CC) capacity regions of a two-user Gaussian Multiple Access Channel(GMAC) have been recently reported. For such a channel, code pairs based on trellis coded modulation are proposed in this paper with MPSK and M-PAM alphabet pairs, for arbitrary values of M,toachieve sum rates close to the CC sum capacity of the GMAC. In particular, the structure of the sum alphabets of M-PSK and M-PAMmalphabet pairs are exploited to prove that, for certain angles of rotation between the alphabets, Ungerboeck labelling on the trellis of each user maximizes the guaranteed squared Euclidean distance of the sum trellis. Hence, such a labelling scheme can be used systematically,to construct trellis code pairs to achieve sum rates close to the CC sum capacity. More importantly, it is shown for the first time that ML decoding complexity at the destination is significantly reduced when M-PAM alphabet pairs are employed with almost no loss in the sum capacity.

Comparative measurements of HV impulses to evaluate different sets of response parameters

Results are reported of comparative measurements made in 14 HV (high-voltage) laboratories in ten different countries. The theory of the proposed methods of characterizing the dynamic behavior is given, and the parameters to be used are discussed. Comparative measurements made using 95 systems based on 53 dividers are analyzed. This analysis shows that many of the system now in use, even though they fulfil the basic response requirements of the standards, do not meet the accuracy requirements. Because no transfer measurements were made between laboratories, there is no way to detect similar errors in both the system under test and the reference system. Hence, the situation may be worse than reported. This has led to the recommendation that comparative measurements should be the main route for quantifying industrial impulse measuring systems

Minimal sets of generators for the relation ideals of certain monomial curves

Let O be a monomial curve in the affine algebraic e-space over a field K and P be the relation ideal of O. If O is defined by a sequence of e positive integers some e - 1 of which form an arithmetic sequence then we construct a minimal set of generators for P and write an explicit formula for mu(P).

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

In this paper we consider the problem of learning an n × n kernel matrix from m(1) similarity matrices under general convex loss. Past research have extensively studied the m = 1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well knownMirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m2 log n 2) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n × n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL,which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVMsolver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

Tree structure for efficient data mining using rough sets

In data mining, an important goal is to generate an abstraction of the data. Such an abstraction helps in reducing the space and search time requirements of the overall decision making process. Further, it is important that the abstraction is generated from the data with a small number of disk scans. We propose a novel data structure, pattern count tree (PC-tree), that can be built by scanning the database only once. PC-tree is a minimal size complete representation of the data and it can be used to represent dynamic databases with the help of knowledge that is either static or changing. We show that further compactness can be achieved by constructing the PC-tree on segmented patterns. We exploit the flexibility offered by rough sets to realize a rough PC-tree and use it for efficient and effective rough classification. To be consistent with the sizes of the branches of the PC-tree, we use upper and lower approximations of feature sets in a manner different from the conventional rough set theory. We conducted experiments using the proposed classification scheme on a large-scale hand-written digit data set. We use the experimental results to establish the efficacy of the proposed approach. (C) 2002 Elsevier Science B.V. All rights reserved.

A Fast Linear Separability Test by Projection of Positive Points on Subspaces

A geometric and non parametric procedure for testing if two finite set of points are linearly separable is proposed. The Linear Separability Test is equivalent to a test that determines if a strictly positive point h > 0 exists in the range of a matrix A (related to the points in the two finite sets). The algorithm proposed in the paper iteratively checks if a strictly positive point exists in a subspace by projecting a strictly positive vector with equal co-ordinates (p), on the subspace. At the end of each iteration, the subspace is reduced to a lower dimensional subspace. The test is completed within r ≤ min(n, d + 1) steps, for both linearly separable and non separable problems (r is the rank of A, n is the number of points and d is the dimension of the space containing the points). The worst case time complexity of the algorithm is O(nr3) and space complexity of the algorithm is O(nd). A small review of some of the prominent algorithms and their time complexities is included. The worst case computational complexity of our algorithm is lower than the worst case computational complexity of Simplex, Perceptron, Support Vector Machine and Convex Hull Algorithms, if d

A general construction of space-time trellis codes for PSK signal sets

The diversity order and coding gain are crucial for the performance of a multiple antenna communication system. It is known that space-time trellis codes (STTC) can be used to achieve these objectives. In particular, we can use STTCs to obtain large coding gains. Many attempts have been made to construct STTCs which achieve full-diversity and good coding gains, though a general method of construction does not exist. Delay diversity code (rate-1) is known to achieve full-diversity, for any number of transmit antennas and any signal set, but does not give a good coding gain. A product distance code based delay diversity scheme (Tarokh, V. et al., IEEE Trans. Inform. Theory, vol.44, p.744-65, 1998) enables one to improve the coding gain and construct STTCs for any given number of states using coding in conjunction with delay diversity; it was stated as an open problem. We achieve such a construction. We assume a shift register based model to construct an STTC for any state complexity. We derive a sufficient condition for this STTC to achieve full-diversity, based on the delay diversity scheme. This condition provides a framework to do coding in conjunction with delay diversity for any signal constellation. Using this condition, we provide a formal rate-1 STTC construction scheme for PSK signal sets, for any number of transmit antennas and any given number of states, which achieves full-diversity and gives a good coding gain.