reconstruction of magnetic resonance imaging ( mri ) from data sampled using noncartesian 
 sampling has recently received increasingly mathematically sophisticated 
 treatment , for example , with notable improvements in reconstruction speed and 
 accuracy .
the application of novel design techniques for noncartesian sampling 
 trajectories , however , has received less attention . in , a novel pseudorandom volumetric k - space trajectory design method was presented . 

this methodology , henceforth referred to as durga , combines a number of ideas 
 in trajectory design and general sampling design for the first time , including 
 randomness , [ 3 , 4 ] constrained optimization 
  to balance 
 trajectories for steady - state imaging [ 69 ] , genetic algorithms , under - sampling to trade 
 acquisition time for ( structured ) noise [ 1113 ] , and target - oriented design rather than patterns of 
 symmetric interleaving [ 14 , 15 ] . by combining these ideas
, durga achieves 
 significantly better efficiency as measured by sampling duty - cycle for a 
 balanced steady - state pulse sequence .
flow - insensitive k - space trajectories are inherently more 
 efficient than trajectories requiring a rewinder to balance first and possibly 
 higher moments .
trajectories which sample three dimensions in k - space , like durga , can further increase 
 efficiency by not rewinding slice select gradients , and simply starting and 
 stopping sampling offset from the center of k - space immediately after and before the 
 excitation pulse .
this is summarized in table 1 by a comparison of spiral with 
 velocity compensating rewinder , teardrop   which incorporates in - plane velocity compensation into 
 the readout , and durga .
these numbers are relative to gradient peak / slew 
 limits of 40 mtm and 150 tms for spiral   and durga  
 and 27 mtm and 72 tms for teardrop .
volumetric imaging has several inherent advantages 
 over thin - slice imaging , including isotropic resolution , reduced effect of 
 in - flow , and the ability to completely correct for distortions in gradients , 
 main - field inhomogeneity , and eddy currents .
it is also easier to completely 
 compensate for velocity effects by nulling higher moments .
moment - nulled planar 
 trajectories are often only effectively nulled in one or two dimensions , 
 because they are used with slice select and possibly phase encoding gradients 
 which are difficult to null . in the case of rapid imaging , however , the most 
 important property of sampling in more dimensions is the ability to under 
 sample without introducing aliasing in the form of ghosts [ 11 , 16 ] . using durga , one can 
 essentially trade off under sampling for unstructured noise on a continuous 
 basis , breaking the dependence on nyquist sampling .
the trajectories used in 
 the illustrations to reconstruct 256 volumes are 33 under sampled in time relative to perfect 
 cartesian sampling ( ignoring gradient limits , and only considering sampling 
 bandwidth ) .
this paper presents two innovations over . 
 a genetic algorithm for choosing subsets of 
 trajectory arcs ( figure 1 ) corresponding to a tr , designed using one of the methods in .
this significantly increases the simplicity and 
 flexibility of implementation and improves the quality of the solution , as 
 measured by the point spread function.multicoil numerical simulations , including the 
 effect of noise , showing low levels of aliasing artifacts with extreme 
 under - sampling . 

although this sampling strategy is compatible with and benefits from multicoil imaging , the 
 reduction in aliasing possible by using an iterative sense reconstruction 
  is much smaller 
 than what could be expected based on experience with other trajectories .
a genetic algorithm for choosing subsets of 
 trajectory arcs ( figure 1 ) corresponding to a tr , designed using one of the methods in .
this significantly increases the simplicity and 
 flexibility of implementation and improves the quality of the solution , as 
 measured by the point spread function .
multicoil numerical simulations , including the 
 effect of noise , showing low levels of aliasing artifacts with extreme 
 under - sampling .
sampling trajectories in 3d k - space are generated by solving a second - order 
 cone optimization problem ( socp ) , originally formulated in .
an socp is a minimization 
 problem in which the variables are constrained to lie inside a set defined by 
 quadratic functions of the variables .
putting a bound on the length of a vector 
 is a common special case , and the one exploited in this trajectory design 
 problem : 
 ( 1)min   , 
 ( 2)k0=0=kn , 
 ( 3)ki+1ki2gmaxt , 
 ( 4)ki+22ki+1+ki2smaxt2 , 
 ( 5)ki21/r , 
 ( 6)i=1ni(ki+1ki)<flow , 
 ( 7)ktigi2<{0gi=0,goalotherwise , where the variables , ki   ,   i = 1 ,  , n  1 , are the position in k - space at time i ;  controls the deviation from the constraints 
 ( 1 ) ; t is the time step ; gmax and smax are peak ( 3 ) and slew ( 4 ) constraints on the 
 gradients ; r is the maximum resolution used in the 
 reconstruction ( 5 ) ; the sum in ( 6 ) models the phase error caused by constant 
 flow  errors from nonconstant flow can be handled by adding norms of higher 
 moments ; gi are the targets near which the trajectory 
 should pass ( 7 ) at time tj , 
 see figure 2 ; and the s determine the relative priorities placed on 
 meeting the different goals . in the trajectories designed for this paper , the goals gj are random points on the boundary sphere |k| = 1/r or at k = 0 . 

multiple traversals of k = 0 are not optimal for sampling , but included to 
 facilitate calibration of gradient distortion and main - field inhomogeneity . 

higher 
 moments , nulling at different points in the trajectory , or bounding the size of 
 the moment with a tolerance could be encoded in the same way .
the trajectories 
 in this paper are designed to begin and end at k = 0 , for steady - state imaging , but this is not a limitation of the method .
see 
  for a detailed 
 description of the software used to solve this optimization problem , and a 
 discussion of variations in the design , including iterative designs in which 
 goals are placed at low - density points for previous trajectories .
note that the 
 constraint on the first moment will cause an optimal trajectory to traverse 
 parts of k - space not near a shortest path between the 
 goals , gi , 
 which increases the coverage of k - space , but there are no explicit objectives 
 for coverage , intertrajectory spacing , or trajectory length
. in , coverage is handled by 
 pseudorandom assignment of goals from the vertices of a regular triangulation 
 of the limit sphere in k - space . in this paper ,
coverage is assured by optimizing its effect on the point spread function 
 ( psf ) , which captures sampling artifacts ( exactly for uniform coils , and 
 approximately for surface coils ) .
the ratio of the l norm of the central point in the psf and the l norm of the rest of the psf is maximized over 
 subsets of a large fixed set of trajectories , each optimized as described 
 above . since the set of subsets of a fixed size grows factorially with the 
 number of trajectories ,
a genetic algorithm 
 uses information about previous subsets to test only subsets likely to have 
 better psfs .
this approach differs from formulations , where the 
 variables ( referred to as chromosomes in genetic algorithms ) are local or 
 nonlocal control points on individual trajectories .
such approaches lead to a 
 much larger search space , and increased complexity of each search step , since 
 the solution of the socp problem is the most expensive part of the 
 optimization . in the present method ,
one socp problem is solved per trajectory 
 ( and may be solved in parallel ) before application of the ga search .
individual trajectories are 5.6 milliseconds , including 0.1 millisecond for rf excitation , and designed 
 with gradient limits typical of a whole body clinical imager ( peak gradient of 40 mtm and a gradient slew rate 150 tms ) . for ease of comparison , we will choose enough trajectories for 1 second of sampling ( 178 with the above parameters ) .
as a first step , many trajectories are designed by 
 randomly selecting goals on the boundary sphere ( which are interleaved with 
 fixed goals at k = 0 ) . of these , many are clearly less suitable 
 than others . to filter out the least suitable , a small number are designed to 
 determine an approximate threshold for the longest 20% , and the 20% closest to their own goals .
this initial large set is then partitioned into 400 sets of the desired size ( 168 ) to seed the ga .
these seed sets are then 
 evolved through 45 generations , using chromosomes consisting of 
 integer indices into the initial set .
an additional 10 trajectories were added using a  density 
 threading  , whose 
 aim is to increase sampling of voids along the kx  ky plane by specifically creating trajectories to 
 pass through areas of low sampling density .
computation time refers to a 
 powermac g5 2.5 , 
 running a c program calling socp , http://www.stanford.edu/~boyd/socp , and the genetic algorithm utility 
 library , http://gaul.sourceforge.net .
the objective of the optimization is to improve 
 the quality of the psf , as measured by fourier transforming the ( weighted ) 
 sampling density , and dividing the central value in the psf by the total 
 energy .
the method of determining the density must be the same as used in 
 reconstructing the images , since different methods can potentially produce 
 different artifacts even with the same trajectories . to calculate the fractional sampling , both in k - space and in time , nearest neighbour 
 resampling was used to calculate a sampling density , and the number of nonzero 
 elements in the k - space array was computed .
for example , 1 second trajectory set , 1.54% of the voxels in a 256 
 k - space had nonzero values , giving one measure 
 of under - sampling .
this corresponds to 51.7% of the number of the samples that would be 
 collected in 1 second with a receiver bandwidth of 500 khz , giving a measure of the efficiency 
 relative to the ( unrealizable ) maximum sampling rate .
numerical 
 simulations were reconstructed by simulating irregularly sampled data ( 500 khz sampling ) along the trajectories .
receiver coils were approximated by 
 magnetic dipoles , with sensitivities evaluated at the center of each phantom 
 cube . in this approximation ,
the signal in k - space corresponding to each cube 
 is a product of sinc functions , scaled by the complex sensitivity value .
the irregular samples were then divided by the 
 sampling density in k - space and resampled to a regular grid using 
 convolution . for multiple coils with sensitivities
si , the transformed images i , were combined with two methods : weighting - by - sensitivities(8)coilssiicoilssisiand conjugate gradient 
 reconstructions .
a lot of analysis has been done on resampling 
 irregular data with density variations , see [ 1820 ] and references therein .
convolution with a fixed 
 kernel   is the 
 simplest resampling method to implement and to analyze .
estimating the density to use for 
 correction was done by resampling a constant set of data points using a 
 width - three triangular kernel .
the key property of this triangular function is 
 that it is a partition of unity for samples spaced 1 , 2 , or 3 grid points apart .
when the described algorithm was used to generate the 168-shot volume representing 1 second of imaging time , 12 hours were taken to create a working base of 4000 trajectories using randomly generated goals . 

another 72 hours were required for the ga to select a fit 
 subset . 

figure 3 compares the results of the ga to a histogram 
 of 3000 randomly formed subsets .
the ga set is 7.8 standard deviations better than the set , and 
 is shown as a banded bar .
also shown is the result of adding 10 density - threaded trajectories . the estimated sampling density used for density 
 correction
the corrected sampling 
 density is shown , in which the uniformity of the bright pixels reflects the 
 quality of the correction . recall that only 1.54% of grid points in k - space contain a sample point at this 
 reconstructed resolution
. a better measure of the quality of the set of 
 trajectories , together with the density correction , is given by the psf ( figure 4 ) , which 
 predicts very little blurring and a low level of noise - like aliasing . because it is difficult to inspect more than a planar 
 cross - section of the psf at a time
, it is hard to appreciate the extent to 
 which the noise - like aliasing accumulates in three dimensions .
this is 
 demonstrated using a numerical phantom consisting of four rings of varying 
 sizes , figure 5 .
the phantom was chosen to be readily identifiable in cross - section , and 
 in volume / surface rendering .
the apparent noise will increase as a function of 
 the total signaling volume ; the phantom represents a midway point between 
 contrast - enhanced mr angiography ( with a small blood volume producing signal ) 
 and anatomical imaging .
four different reconstructions of the central x - y cross - section are shown in figure 6 .
the uniform reconstruction shows 
 significantly more alias noise in the periphery of the image than the 32 surface - coil reconstruction . for measurement 
 noise , this is as expected , since the coils are more sensitive near the 
 periphery . for the noise - like aliasing artifact ,
the true image is multiplied by the coil sensitivity , which is then 
 corrected when performing multicoil combination .
the artifacts are also 
 modulated by the sensitivity , but since they are delocalized ( by definition ) , 
 they are not corrected during combination , and hence partially cancel each 
 other out .
this is more apparent where the sensitivities vary ( the periphery ) 
 than where they are relatively uniform ( the center ) .
the noisy multiple and single surface coil images 
 ( lower row ) show typical loss of sensitivity by the center of the phantom for a 
 single channel , which is reduced in the combined image .
the 32-coil noisy image shows visually equal noise 
 levels to the first two images , but with different ( higher ) frequency 
 composition .
iterative methods have been successfully used in 
 planar imaging to reduce spiral artifacts by using a priori information about 
 multiple coil sensitivities , notably using the conjugate gradient method 
 .
what it can do is reducing 
 the effect of blurring , as is visible in the reconstruction of a 16 voxel uniform box .
figure 7 shows the result of 
 the first step common to steepest - descent and the conjugate gradient method .
figure 8 shows the residual decreasing for 
 the first step , and starting to diverge thereafter , with two coil 
 configurations , and simple and complex phantoms .
adapted methods have been proposed for ill - posedness   and round - off errors 
 , but are beyond 
 the scope of this paper .
a common cross - section is displayed of the original 
 solution , the result after one step , and a scaled version of the gradient 
 ( using , in the electronic edition , different colors for positive and negative 
 pixel values ) . what aliasing artifact is present is either unchanged or 
 enhanced by the gradient step , while softening of the edges is clearly reduced .
the psf and 
 numerical phantoms presented here show that durga is a very promising approach 
 to designing trajectories for volumetric imaging .
pseudorandom trajectory 
 design visibly eliminates coherent aliasing artifacts in numerical simulations . using the ga increases the flexibility of this method 
 and increases the quality of the solutions .
there is a marked difference in 
 quality between randomly generating subsets and using the ga to improve a 
 population . after filtering out inferior individual trajectories , randomly 
 selecting subsets produced surprisingly little variation in the quality of the 
 psf .
initial attempts in using genetic algorithms based on randomly chosen 
 initial points and unfiltered trajectories were not able to beat the heuristic 
 in , so success of 
 the ga depends very much on a careful formulation , and even then , it is 
 unlikely that the global optimum will be reached . unfortunately , it is also 
 considerably more expensive .
the modest improvement produced by steepest descent 
 means that the sampling patterns are so efficient that little additional 
 information can be extracted by a parallel reconstruction taking advantage of 
 geometric coil information , at least with the present coils .
we conjecture that 
 the randomness optimized to make the psf flat produces a large cluster of small 
 eigenvalues in the operator being iterated in the cg step , causing the cg to 
 begin diverging after one iteration .
we are planning modifications of the basic trajectory 
 design to quantify the first effect , and working with partners to collect data 
 to evaluate the second . in any case ,
multiple coil reconstruction using coil 
 sensitivities does reduce the apparent noise , which is important to end users .
we will also investigate compressed sensing 
 reconstructions 
 which require incoherent aliasing artifacts such as those presented in this 
 work , because in such cases  randomness is too important to be left to 
 chance  .
 a pseudorandom , velocity - insensitive , volumetric k - space sampling trajectory is designed for use with balanced steady - state magnetic resonance imaging . 
 individual arcs are designed independently and do not fit together in the way that multishot spiral , radial or echo - planar trajectories do . 
 previously , it was shown that second - order cone optimization problems can be defined for each arc independent of the others , that nulling of zeroth and higher moments can be encoded as constraints , and that individual arcs can be optimized in seconds . 
 for use in steady - state imaging , sampling duty cycles are predicted to exceed 95 percent . 
 using such pseudorandom trajectories , aliasing caused by under - sampling manifests itself as incoherent noise . in this paper , a genetic algorithm ( ga ) is formulated and numerically evaluated . 
 a large set of arcs is designed using previous methods , and the ga choses particular fit subsets of a given size , corresponding to a desired acquisition time . 
 numerical simulations of 1 second acquisitions show good detail and acceptable noise for large - volume imaging with 32 coils . 
1. INTRODUCTION
2. METHODS
3. RESULTS
4. DISCUSSION