{'fraction_non_alphanumeric': 0.03519015921211414, 'fraction_numerical': 0.015181595235314727, 'mean_word_length': 4.673586572438163, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Search strategies for long gravitational-wave transients: hidden Markov model tracking and seedless clustering

A number of detections have been made in the past few years of gravitational waves from compact binary coalescences. While there exist well-understood waveform models for signals from compact binary coalescences, many sources of gravitational waves are not well modeled, including potential long-transient signals from a binary neutron star post-merger remnant. Searching for these sources requires robust detection algorithms that make minimal assumptions about any potential signals. In this paper, we compare two unmodeled search schemes for long-transient gravitational waves, operating on cross-power spectrograms. One is an efficient algorithm first implemented for continuous wave searches, based on a hidden Markov model. The other is a seedless clustering method, which has been used in transient gravitational wave analysis in the past. We quantify the performance of both algorithms, including sensitivity and computational cost, by simulating synthetic signals with a special focus on sources like binary neutron star post-merger remnants. We demonstrate that the hidden Markov model tracking is a good option in model-agnostic searches for low signal-to-noise ratio signals. We also show that it can outperform the seedless method for certain categories of signals while also being computationally more efficient.


I. INTRODUCTION
The discoveries of gravitational waves (GW) by Advanced Laser Interferometer Gravitational Wave Observatory (Advanced LIGO) and Advanced Virgo detectors [1,2] have opened the new window for gravitational wave astrophysics. At the end of the second observing run (O2), LIGO and Virgo have observed multiple binary black hole (BBH) coalescences [3] and one binary neutron star (BNS) merger GW170817 [4], with the latter marking the advent of multi-messenger astronomy [5].
There is also considerable interest in understanding the fate of the BNS merger remnant. In particular, searches have been carried out using O2 interferometric data from LIGO, Virgo, and GEO600 for GW signals from a possible short, intermediate, or long lived remnant of GW170817 with timescales of order of 1 s, 100-1000 s and 1000 s respectively [6][7][8]. Since the nature of the remnant and the exact form of GW emission is unknown, unmodeled searches have played a large role in the analysis. The Stochastic Transient Analysis Multi-detector Pipeline (STAMP), which searches for excess GW power in spectrograms of cross-correlated data, has been employed in both intermediate and long duration searches. These spectrograms are parsed by pattern recognition algorithms for GW signals. Several such algorithms have been proposed in the past; they can be broadly categorized as seed-based and seedless [9][10][11][12]. Seed-based algorithms identify loud seed pixels in the spectrogram (above some threshold) * banag002@umn.edu † lssun@caltech.edu and attempt to grow contiguous clusters from them by adding neighboring pixels. Seedless algorithms picks out clusters by drawing tracks from some predefined template bank. Since they do not depend on initial loud pixels, they are generally more sensitive than seeded algorithms, especially towards towards narrowband waveform models albeit at a higher computational cost [11,13]. Seedless algorithms have to compromise between computational cost and sensitivity to waveform morphology -for example the implementations of seedless algorithms in [6,8] adopt quadratic fitting in the time-frequency spectrograms.
Here, we apply a hidden Markov model (HMM) tracking algorithm -first implemented for continuous gravitational wave searches in Refs. [14][15][16] -to cross-correlated data. HMM-based tracking in frequency domain provides accurate estimates of the signal frequency at low signal-tonoise ratio (SNR) when a large number of observational samples are available [17,18]. In the GW context, it was applied in the first observing run (O1) of Advanced LIGO to search for continuous waves from the brightest lowmass X-ray binary, Scorpius X-1 [19]. A revised HMM was used to search for signals from a long-lived post-merger remnant of the binary neutron star merger GW170817 [8,20]. We apply this algorithm to the cross-power maps produced by STAMP and make a quantitative comparison between the performance of HMM and the seedless algorithm. We demonstrate that HMM can outperform seedless algorithms for specific waveform models, and in particular for models used in post-merger remnant searches [21].
The rest of the paper is organized as follows. In Sec. II, we briefly describe the cross-power maps, the pixel SNR statistic and the detection statistic. In Sec. III, we describe the two methods being compared -HMM tracking and the seedless clustering algorithms. In Sec. IV, we compare the detection efficiency and computational cost of the two algorithms for a variety of waveform models, and demonstrate that the HMM tracking generally outperforms in both aspects. A summary of the paper is given in Sec. V.

II. CROSS-POWER MAP
Unmodeled transient searches with STAMP are usually done on spectrograms of cross-power. They are constructed by cross-correlating data between two GW detectors in the frequency domain. We follow the definition in Ref. [12] and construct normalized cross-power spectrograms as follows: wheres I (t; f ) is the discrete Fourier transform of data from detector I calculated over some segment duration T , P I (t; f ) is the noise power spectral density (PSD) in detector I, denotes the real part of a complex number andQ(t; f,n) is a complex filter function which helps "point" the detectors in direction ofn as seen from Earth. Since ρ(t; f,n) has been normalized with the noise PSD, it is called the pixel SNR. Cross-power spectrograms such as in Fig. 1 are made by repeating this over many segments of data. Pattern recognition or clustering algorithms pick out a cluster of pixels in the spectrogram, representing a possible signal, e.g., one monotonically evolving in frequency. The SNRs of these pixels are then summed up to give the detection statistic. The normalized cluster SNR of the track, Γ c is given by where i indexes over all the pixels in the cluster c, and N is an empirically chosen normalization factor. Γ c plays the role of the detection statistic. The cluster with the largest Γ c will be the trigger for the spectrogram, and the distribution of Γ c is computed for spectrograms containing pure noise to measure the background for the search. A good clustering algorithm finds an optimal cluster which samples as much of a potential signal as possible, without a corresponding increase in the background.

III. CLUSTERING ALGORITHMS
In this section, we describe the two clustering algorithms we use here, HMM tracking (Sec. III A) and seedless clustering (Sec. III B), using the cross-power spectrograms computed as described in Sec. II.

A. HMM tracking
A HMM is a memory-less, probabilistic state automaton based on a Markov process, composed of the hidden state variable q(t) ∈ {q 1 , · · · , q N Q } and the measurement variable o(t) ∈ {o 1 , · · · , o N O } sampled at discrete times t ∈ {t 0 , · · · , t N T }. A full description of HMM formulation and the computationally efficient Viterbi algorithm [22] used for solving the HMM can be found in Ref. [14].
We track q(t) = f gw (t) in a Markov chain, where f gw (t) is the GW frequency at time t. The discrete hidden states q i are mapped one-to-one to the frequency bins in the cross-power map, with bin size ∆f = m/T , where m is a coarse-graining integer coefficient (see Sec. IV A). We choose a constant k to satisfy for 0 ≤ t ≤ T obs , whereḟ gw is the first time derivative of the GW signal frequency. The HMM emission probability at each discrete time, defined as the likelihood of hidden state q i being observed in state o j , is given by [14] L Here we leverage the cross-power pixel SNR in Eqn. (1), and define the emission probability over each time interval [t, t + T ] as We also choose T ≤ 100 s such that the Earth rotation can be neglected during the interval [t, t + T ] in the frequency range of interest. The transition probability of q i from time t n to t n+1 is defined as [14] A which depends on the signal evolution characteristics.
Here we consider a model-agnostic, long-transient signal whose frequency rapidly decreases, e.g., a signal from a binary neutron star post-merger remnant. Assuming that the signal frequency can be approximated by a negatively biased random walk, with frequency change over each segment T , i.e., f gw (t n )−f gw (t n+1 ), uniformly distributed in range [0, km/T ], we adopt the transition probabilities with all other entries being zero. In Eqn. (8), j takes integer values 0 ≤ j ≤ k − 1. We can always adjust Eqn. (7) in searches for other types of signals. Since we have no independent knowledge of f gw , we choose a uniform prior, viz.
The probability that a hidden state path Q = The most probable Viterbi path is the maximum a posteriori track, which maximizes P (Q|O). The detection statistic is the cluster SNR as defined by Eqn.

B. Seedless clustering
We now briefly describe the seedless clustering algorithm following Refs. [11,13]. The algorithm attempts to pick out the morphology of a potential signal in the crosspower spectrogram by drawing tracks from a template base. In principle the template could have any possible form. In the case of compact binary coalescence sources for example, one could employ very specific templates drawing upon precise models of GW radiation from them [23,24]. Yet, in presence of uncertainty about the sources and morphology of astrophysical signals, using quadratic Bézier curves is a good tradeoff between sensitivity and computational cost. Quadratic Bézier curves provide good sensitivity to many monotonically evolving waveform models, and have been applied in several searches conducted in the past [6,8,25].
In practice we pick three points (i.e., three pixels) randomly within the spectrogram with the only condition being that the frequency evolution between them be monotonic. The three pixels N i = (f i , t i ) are then fit with quadratic curves parameterized by ξ: Each Bézier template is defined as one choice of (N 0 , N 1 , N 2 ), which completely describe a quadratic curve in Eqn (11). Usually a total number of templates N temp ∼ 10 6 are used for a single spectrogram. The SNR for the cluster obtained from one template, Γ c , is defined as the sum of the SNRs of all pixels along the quadratic curve, and is again calculated using Eqn. (2). These are the triggers for the search and the loudest trigger for a spectrogram is picked as the prospective signal candidate for further scrutiny.

A. Sensitivity analysis
In this section, we compare the sensitivities obtained from HMM tracking and seedless clustering. We make comparisons using two different sizes of spectrograms. The "long duration" spectrograms are 15,000 seconds long, made of short Fourier transforms (SFTs) of 100 seconds of data coarse-grained to 1-Hz frequency resolution. The same configuration of spectrograms has been used in Ref. [8] to search for long-duration post-merger remnant signals. The "intermediate duration" spectrograms are 500 seconds long with 1 s SFTs and 1 Hz bin sizes. Spectrograms of this intermediate size have been used extensively in the past [26], most recently in Refs. [6,25]. For each configuration, we make a comparison between the two algorithms using (1) Gaussian data recolored to the PSD of the first observing run (O1) of Advanced LIGO, and (2) O2 data from Advanced LIGO Hanford and Livingston detectors, with an unphysical time shift between them [27]. The former sets an ideal scenario for comparison, while the latter aims to accurately capture the impact of non-Gaussian, non-stationary artifacts in real interferometer data.
The long and intermediate duration analyses are described in Secs. IV C and IV D, respectively, while the waveform models used for simulated signals are described in IV B. For the sake of simplicity and for reducing the computational cost, we fix the sky position of all simulated signals to be the same as GW170817 [5], and it is also assumed to be known in the search. All comparisons of sensitivities are made at a false alarm probability (FAP) less than 10 −4 . Finally, the search configurations used for HMM tracking and seedless clustering are listed in Table I (3)], and total number of seedless templates used.

Magnetar Model
For both the long and intermediate-duration spectrograms, we simulate synthetic signals using a neutron star spin-down model, although the search itself is modelagnostic. This model characterizes the gravitational wave radiation from an nonaxisymmetric long-lived post-merger remnant. The remnant might be spinning down due to GW radiation or electromagnetic radiation or some combination thereof. This model has been used in setting limits for post-merger GW emission from GW170817 in both the intermediate-duration and long-duration searches [6,8]. The frequency evolution of the rapidly spinning down signal is given by [28]: where n is the braking index defined viaḟ gw ∝ f n gw , τ is the spin-down timescale and f gw (0) is the starting frequency at reference time t = 0. The gravitational-wave strain amplitude is given by [28]: where G is Newton's gravitational constant, c is the speed of light, I zz is the principal moment of inertia of the neutron star, is its equatorial ellipticity, and D is the distance to the source. In Table II, rows 1-2 and 3-4 list the parameters of the synthetic magnetar signals in the long and intermediateduration analyses, respectively. For all models, detection efficiency is defined as the fraction of injected signals recovered at particular root-sum-squared strain amplitude, h rss , given a FAP. In the frequency domain, h rss is defined where h + and h × are strain amplitudes of the waveform in frequency domain for the + and × polarizations, respectively, and f min and f max are the minimum and maximum frequencies of the waveform in the frequency band being analyzed, respectively.

Accretion Disk Instability Model
For intermediate-duration spectrograms, we also test with a different model based on instabilities of accretion disks (ADI) around black holes. These waveforms are parameterized by the mass of the blackhole M BH , dimensionless Kerr spin parameter a * , and the fraction of mass forming inhomogeneities in the disk η. The inhomogeneities are modeled to behave as a binary system and act as a source of gravitational waves. We refer to Refs. [26,29,30] and the references therein for more details about these waveforms. The last two rows in Tables II list the parameters of the ADI signals simulated.
Model spectrograms of the waveforms models used in this paper are shown in the appendix A C. Long duration Fig. 2 presents the detection efficiency as a function of h rss for HMM tracking and seedless clustering, generated by injecting synthetic signals in Gaussian data recolored with O1 noise PSD (top panels) and real time-shifted O2 data (bottom panels). The dashed and solid curves Detection efficiencies (i.e., the rates of correctly recovering injections) for long-duration simulations based on the magnetar models E and M. HMM tracking generally performs better than seedless clustering for these waveforms. The top panels are from simulations in Gaussian noise. The bottom panels are from the same simulated signals injected into time-shifted real O2 data. The results demonstrate that the gain in sensitivity from HMM tracking is not affected by non-Gaussian, non-stationary noise in real interferometric data. We note that the Gaussian data is recolored with O1 noise PSD, and the real data is from the O2 run. The colored regions represent 1σ binomial uncertainty in detection efficiency.
indicate results from HMM tracking and seedless clustering, respectively. We see that HMM tracking outperforms seedless clustering (N temp = 10 6 ). For example, the strain h rss needed by HMM for an efficiency of 0.9 is lower than seedless by about a factor of two in all cases in Fig. 2. A part of the gain comes from the fact that magnetar signal curves are non-quadratic. The quadratic Bézier curves used in seedless clustering do not fit the signal well, while the HMM tracking does not assume a particular shape of the signal curve. One can expect that a better template (for instance a template made of cubic Bézier curves or from the waveform model itself) will give better sensitivity, albeit at a substantial increase in computational cost or loss in sensitivity to other waveforms. We also compare the sensitivity obtained here using HMM tracking with cross-power spectrograms to the ex-isting HMM method used in Ref. [8], which operates on normalized power in SFTs summed over multiple detectors, i.e., Xx X ix X * i , where i indexes the frequency bins of the normalized SFTx, and X indexes the detector [20]. With simulations done on time-shifted O2 data, we compute the 90% sensitive distance, d 90% , i.e., the largest distance at which 90% of the injected signals can be recovered for HMM run on cross-power spectrograms. Using the same moment of inertia of 4.38 × 10 38 kg m 2 and the maximum possible as described in Ref. [8], we obtain d 90% ≈ 0.5 Mpc and 0.2 Mpc for magnetar E and M models, respectively. This is done by calculating h 0 corresponding to the h rss value required for 90% efficiency, and using Eqn. (13) to convert h 0 to the limit on distance. While these are still astrophysically unrealistic distances for a source like GW170817, they are significantly better Note that there are some differences between the simulations in this paper and in Ref. [8]: (1) We use braking index of n = 2.5 here as opposed to n = 5 in [8]; (2) We use cos ι = 1 (the inclination of the source) here as opposed to randomized cos ι in [8]; (3) The FAP in this paper and in [8] are ≤ 10 −4 and 10 −2 , respectively. Although setting cos ι = 1 can improve d 90% by a factor of 2-3 compared to randomized cos ι, d 90% for signals with n = 5 are generally better than n = 2.5 by a factor of < 2 [20]. Combined with the much more stringent FAP adopted in this paper, these results demonstrate that using HMM operated on cross-correlated spectrograms outperforms its usage on incoherent SFT powers from two detectors. The improvement is not unexpected given that the cross-power SNR statistic demands that the phase difference of the signals between two detectors be consistent with the sky position [see Eqn. (1)], whereas the SFT power spectrograms effectively marginalize over the phase and the sky position [20]. A more detailed study of the difference between cross-power and SFT spectrograms is out of the scope of this paper. Fig. 3 shows the relative performance of HMM and seedless clustering using magnetar models A and B, in both recolored Gaussian noise (O1 PSD) and O2 real interferometric data. HMM tracking still outperforms seedless clustering, although in these intermediate-duration simulations in read data, the sensitivity gain from HMM is not as significant as the long-duration search. The same intermediate-duration search configuration (column 3 in Table I) is used for recovering ADI simulations. For illustration purpose, we perform the ADI simulations in Gaussian noise only. The detection efficiencies for these waveforms are shown in Fig. 4. For the ADI models, the recovery efficiencies from HMM tracking and seedless clustering are generally comparable. Unlike the magnetar models described above, the ADI signal waveforms are better sampled by quadratic Bézier curves, and hence seedless is expected to produce similar sensitivity as to HMM.

E. Computing cost
We have demonstrated that HMM tracking provides detection efficiencies better than or at least comparable to seedless clustering in the parameter space considered here. In this section, we show that HMM tracking significantly outperforms seedless clustering with respect to run time and computational cost, and briefly explain the reason.
We have tested the run time of both HMM and seedless methods (with identical scenarios and configurations) for both the intermediate and long-duration spectrograms. Over 2500 realizations of the intermediate-duration spectrograms, the median run time of HMM tracking was ∼ 35 times shorter than seedless clustering with 10 6 templates (see Table. III). A similar test for the long-duration spectrograms produces an improvement of a factor of ∼ 23 for HMM compared to seedless. The gain is less significant in long-duration spectrograms probably because the coarsegrained long-duration spectrograms consist of a smaller number of pixels, N pixel , compared to the intermediateduration spectrogram (see N pixel in Table. III). Although the amount of raw data in the 15,000 second long spectrograms is much larger than the intermediate-duration ones, coarse-graining is generally employed [31] to reduce the volume of data being analyzed. Coarse-graining is done by averaging both the cross and auto-power in finer frequency bins to give coarser bins. While averaging reduces the computational cost of analyzing long duration spectrograms, it also leads to a loss of sensitivity. The natural Fourier transform frequency resolution of 1/T = 10 mHz (T = 100 s) in the long-duration spectrograms would re-quire a prohibitively large number of seedless templates for analysis. The efficiency of HMM tracking makes it a promising tool to run deeper searches over spectrograms with finer frequency resolution.
We now briefly discuss the reason why using HMM shows a significant improvement in computational cost. The HMM tracking uses the dynamic programming algorithm, Viterbi, which reduces the total number of comparisons required to find the optimal path from N N T +1 Q to (N T + 1)N 2 Q in a spectrogram with N pixel = N Q N T [14,18]. When matrix A qj qi only contains ten non-zero terms along the diagonal, the total number of comparisons reduces to 10N pixel . Hence in the intermediate and long duration spectrograms, the total numbers of comparisons are 8.9 × 10 6 and 2.7 × 10 6 , respectively. As a dynamic process, at each step, the algorithm only records 10N Q = 1.8 × 10 4 paths for both configurations, but effectively ensures that the optimal one is kept. This is significantly more efficient than fitting 10 6 curves and summing up the N T SNR pixels for each curve as is done in seedless.

V. CONCLUSION
In this paper, we describe two clustering strategies for long-transient gravitational-wave searches, both operating on pre-calculated, cross-power spectrograms. We conduct large number of simulations for both long-duration (15000 s) and intermediate-duration (500 s) signals in both Gaussian noise and real interferometric data. In the simulations and comparison carried out in this paper, we mainly focus on the magnetar model that is adopted in BNS post-merger remnant and other long-transient searches. We have demonstrated that HMM tracking can produce detection efficiency better than or at least similar to seedless clustering, and reduce the computing cost significantly, based on the same sets of spectrograms. HMM tracking can also be applied to track a variety of signal models in addition to the ones tested above, e.g., nonmonotonic signals, by adjusting transition probabilities (see Ref. [16]). In addition, a small improvement in the sensitive distance will give a relatively large improvement in sensitive volume. With much lower computational requirements, HMM tracking method can be a good option in unmodeled all-sky searches for long-transient signals.
In model-agnostic, computationally challenging searches, HMM tracking can prove to be a superior strategy to parse spectrograms.
The HMM tracking algorithm operated on cross-power spectrograms also outperforms the existing HMM tracking operated on SFT power spectrograms used in previous searches for long-duration BNS post-merger signals [8].
This new implementation can serve as a more sensitive and efficient alternative in future analyses of the same kind. Finally, this work might also open the window to otherwise prohibitively expensive all-sky long-duration searches (with ∼ 10 4 -s or longer spectrograms), given the significant reduction in computational cost by using HMM tracking.

VI. ACKNOWLEDGMENTS
We are grateful to Maxime Fays, Rich Ormiston, Stuart Anderson and Vuk Mandic for comments and informative discussions. S. Banagiri acknowledges support in part by the Hoff Lu Fellowship at the university of Minnesota, and by NSF grant PHY-1806630. L. Sun is a member of the LIGO Laboratory. M. W. Coughlin is supported by the David and Ellen Lee Postdoctoral Fellowship at the California Institute of Technology. The authors are thankful for the computing resources provided by LIGO Laboratory. LIGO was constructed by the California Institute of Technology and Massachusetts Institute of Technology with funding from the National Science Foundation, and operates under cooperative agreement PHY-0757058. Advanced LIGO was built under award PHY-0823459. The research was also supported by Australian Research Council (ARC) Discovery Project DP170103625 and the ARC Centre of Excellence for Gravitational Wave Discovery CE170100004. This paper carries LIGO Document Number LIGO-P1900047.

Appendix A: Spectrograms
We show sample spectrograms of the waveform models used in this study in Fig. 5 for the long-duration spectrograms and Figs. 6-7 for the intermediate-duration ones.