\section{Introduction}

    Gait analysis, focusing on the pattern of body movement during walking or running, has received increasing attention in recent years \cite{gafurov2007survey, wan2018survey}. There are two popular approaches used to analyze gait data. The first is video-based, which uses external cameras to record videos that directly capture body movements \cite{lee2002gait, niyogi1994analyzing}. The second is sensor-based, which analyzes signals from sensors that are attached to the human's body \cite{hou2014systemforhumangait}. Accelerometers, as a common built-in sensor in mobile devices, have become one of the most popular sensors in sensor-based gait analysis \cite{tamviruzzaman2009epetwhen}.

    Prior studies \cite{gafurov2007gaitauthen, mantyjarvi2005identifyingusers} have found that there are repetitive patterns in accelerometer signals that correspond  to two foot steps and constitute a gait cycle. These studies presented methods to detect the gait cycle, created templates or extracted features from the cycle, and matched feature vectors or templates for recognition. However, using the entire gait cycle to create templates requires much training data and a lot of computation time, which is less efficient for mobile devices. Also, aggregate gait features, such as the minimum and maximum of the whole gait cycle, cycle length, and velocity \cite{anwary2018automatic}, miss critical structural information of gait cycles. Thus, they may not represent gait information precisely and are easy to be imitated. Some studies \cite{bejarano2014novel, Maqbool2017realtime} associated "Heel contact" and "Toe off", which are two essential foot events that occur within the gait cycle, with accelerometer signals to help detect gait cycles and extract more accurate features. These two events divide the gait cycle into the stance phase, where accelerometer signals remain almost constant, and the swing phase, where accelerometer signals vary greatly. However, these studies didn't explain why these events match the points in accelerometer readings, what foot events occurred during the swing phase, and why accelerometer signals vary a lot in this period. We define a structure that consists of the swing phase, including the raising of the foot, flight of the foot, and lowering of the foot, and relate it to the changes in accelerometer signals. This structure appears in every gait cycle.

    The main contributions of this paper are as follows:
    \begin{itemize}\label{contribution}
        \item We formally define a standard structure within gait cycles from accelerometer signals, called PQRST Complex.
        It captures the most representative and persistent part of the walking patterns because the rate of change in accelerometer readings in the swing phase is very high as compared to the stance phase.
        \item We present nine features using the PQRST Complex that capture the gait cycle's change points, thus capturing variations within the cycle.
        \item We achieved an average correct classification rate (CCR)\label{abbr:CCR} of 90.51\% on an authentication system using PQRST Complex with performance better than most previous research with a smaller set of features.
    \end{itemize}

    The rest of this paper is organized as follows. Section \ref{sec:relatedwork} shows prior works in this field. In Section \ref{sec:PQRSTcomplex}, we describe the definition of the PQRST Complex and analyze features extracted from it in detail. The performance evaluation is displayed in Section \ref{sec:exp}. Finally, we conclude our work in Section \ref{sec:conclusion}.

\section{Related work}\label{sec:relatedwork}

    Signals from the accelerometer readings can be used to analyze gait \cite{ailisto2005identifying, annadhorai2008human, derawi2012smartphones}. Several methods for gait cycle detection and recognition have been proposed in the last decade. Gafurov \etal \cite{gafurov2007gaitauthen, gafurov2007spoof, gafurov2006robustness} proposed a straightforward method for gait cycle detection with an assumption that the minimas in accelerometer signals are the starting points and ending points for each gait cycle, and each cycle contains two steps. They used six consecutive cycles and used the median points of these cycles to create a feature vector and achieved a 86.3\% recognition rate. Derawi \etal \cite{Derawi2010Improved} presented an improved cycle detection method on accelerometer signals. Besides using the same assumption as Gafurov \etal \cite{gafurov2007gaitauthen}, they combined estimated cycle length (the length of one gait cycle usually varies between 800 ms - 1400 ms) and Neighbour Search to find all minimum points and utilized all detected cycles to create templates. They proposed the cyclic rotation metric (CRM)\label{abbr:CRM} to measure the distance between input samples and templates for authentication. The lowest Equal Error Rate (EER) they achieved was 5.7\%. Rong \etal \cite{Rong2007Identification} presented a gait cycle partition method and gait recognition algorithm based on Dynamic Time Warping (DTW)\label{abbr:DTW}. They used the first zero value point right after the local minimum point as the starting and ending points to separate gait cycles, and defined one gait cycle consisting of four consecutive points of zero value. They applied a time-warping network on the gait cycle they defined to create a gait feature code for each cycle, and used it for their gait recognition algorithm. They got 6.7\% EER in their recognition system. All of the methods mentioned above considered one gait cycle as a whole. They created templates from detected cycles and measured the distance between cycles from input samples and templates by using similarity-based or distance-based methods. Although they achieved relatively low EER in gait recognition or authentication, it was time-consuming to compare distance between template as each template consists of around 100 points. Moreover, none of them have given a standard structure of gait cycles. They only detected the gait cycle with starting points and end points without caring about the exact patterns that gait cycles contain.
    On the other hand, aggregate feature-based studies used features extracted from gait cycles to create feature vectors. Alobaidi \etal \cite{alobaidi2022real} extracted more than 300 features in both time domain and frequency domain, including mean, standard deviation, median, etc., of the gait cycle for activity classification. They got an average EER of 11.38\% in recognizing normal walking activity.

    As Neumann \cite{neumann2010kinesiology} illustrated in his book, human walking consists of a cyclic series of movements. In general, the gait cycle begins with the foot (heel) contacting the ground, continues as the foot (toe) leaving the ground, and ends with the same foot (heel) contacting the ground again. Thus, the beginning and end of the gait cycle are usually referred to as heel contact (HC). The toe leaving the ground separates the gait cycle into two phases: the stance phase and the swing phase. It makes these two foot events crucial for gait cycle detection. Some studies \cite{bejarano2014novel,Maqbool2017realtime} found these two events could be located in accelerometer signals to help them detect the gait cycle and estimate velocity. However, some other small foot events may also affect the changes of accelerometer signals, such as the raising of the foot, flight of the foot, and lowering of the foot during the swing phase. To the best of our knowledge, only a few studies have investigated these small events within the gait cycle. Anwary \etal \cite{anwary2021Insolebased, anwary2018automatic} found that eight foot events can be located in accelerometer signal collected from an accelerometer attached to shoes. They observed that the part where accelerometer signals vary greatly corresponds to the swing phase, and they used this observation to separate the stance and swing phases for step detection. Their results showed that this part of acceleration signal could be used to estimate the swing phase, step length, and velocity. However, they only focused on the terminal stance and toe-off events detection. They did not analyze the structure of these changes and how these foot events relate to the signal, so the gait events they separated were not accurate. In addition, accelerometer signals vary significantly in the swing phase and remain almost constant in the stance phase, and the swing phase only accounts for 40\% of the whole cycle. It suggests that it may be possible to discard 60\% of the gait cycle (stance phase) and focus on only 40\% of the gait cycle (swing phase) to improve the recognition efficiency. The structure we captured matches the swing phase. It captures the foot movements during this period, and we give an explicit explanation of why and how they are matched.

    Many accelerometer-based gait authentication systems have been proposed in recent years and got promising performance. Mufandaidza \etal \cite{mufandaidza2018continuous} developed a smartphone user authentication system using raw accelerometer data. They used the DTW algorithm to synchronize the accelerometer data from all three axes and fed them into a feed-forward neural network. The best True Positive Rate (TPR)\label{abbr:TPR} they got was 73.68\%, and the lowest False Positive Rate (FPR)\label{abbr:FPR} they got was 22.22\%. Some studies have proposed gait cycle based authentication systems. Thang \etal \cite{thang2012gait} presented two approaches for identification based on gait using accelerometer data. Their first approach extracted average gait cycles, which they called time domain features, and used DTW for comparison. The average accuracy they got was 79.1\%. Their second approach used Fast Fourier Transform (FFT) to extract frequency domain features and used Support Vector Machine (SVM) to classify feature vectors. They got an average CCR of 92.7\%. Nickel \cite{nickel2012accelerometer} constructed an accelerometer-based gait authentication on the smartphone. They came up with a cycle-based method, which used raw gait cycle data combined with some features extracted by fixed-length time interval segmentation. They used some machine learning algorithms for classification, and their methods had a low EER, which was around 6\% to 7\%.

\section{Capturing the PQRST Complex structure from accelerometer signal in gait} \label{sec:PQRSTcomplex}

\subsection{Capturing the PQRST Complex structure in accelerometer signal}

    \begin{figure}[ht]
        \centering
        \includegraphics[width=\columnwidth]{Figures/Accelerometer2PQRST2Cycle.pdf}%
        \caption{\textbf{(Top):} Accelerometer signal ("Acc\_X") plot from subject 3.  \textbf{(Middle):} One of the repetitive patterns of accelerometer signal ("Acc\_X") plot from subject 3. The PQRST Complex is captured and marked by red points. Features that we extract from this structure are also marked. \textbf{(Bottom):} Events, which one gait walking cycle includes, match the accelerometer signal. The PQRST Complex corresponds to the swing phase during the walking cycle.}
        \label{fig:accX2PQRST}
    \end{figure}

    The accelerometer has three axes, in the rest of this paper, we use "Acc\_X" to represent the data of the x-axis of the accelerometer, and "Acc\_Y" and "Acc\_Z" are used to represent the data of the y-axis and the z-axis of the accelerometer respectively. The x-axis of accelerometer signal plots are the time with unit 10 ms, and the y-axis is the acceleration value with the unit $m/s^2$.

    \subsubsection{How is PQRST Complex defined?}

   We explain the following structure on a representative subject -- subject 3 from our dataset. Figure \ref{fig:accX2PQRST} (Top) displays the plot for "Acc\_X" from subject 3. It shows repetitive patterns in the accelerometer signal. As Mantyjarvi \etal \cite{mantyjarvi2005identifyingusers} presented, these repetitive patterns represent walking cycles. To take a closer look at the structure of each walking cycle, we zoom in on one of the repetitive cycles and put it in the middle part of Figure \ref{fig:accX2PQRST}. As Anwary \etal \cite{anwary2021Insolebased} mentioned in their work, signals from the accelerometer attached to shoes are relatively steady in the stance phase when compared to the swing phase. In our study, we use accelerometer signals from phones that are placed in pants pocket. We observe that these signals also have a steady part corresponding to the stance phase and a fluctuating part corresponding to the swing phase. Figure \ref{fig:accX2PQRST} (Middle) illustrates this observation. The middle portion shows the swing phase, on which we define the PQRST complex.
    Signals before the point $P$ and after the point $T$ do not fluctuate much. It means that they match the stance phase since the foot that contacts the ground is stationary to support the body in this period. Point $P$ corresponds to the "Toe off" event. After this point, the foot starts to swing and enters the swing phase. The swing phase will end when the event "Heel contact" takes place, and the point $T$ matches this event. Since acceleration values vary a lot between $P$ and $T$, intuitively, this section of the signal would be a rich source of information for feature extraction and authentication.

    According to the variation of the acceleration values, the swing phase can be divided into several short periods. After the point $P$, the foot starts moving forward and upward, which leads to a speed up. It matches the $PQ$ part, where the acceleration increases. As the foot moves forward and upward, it will eventually become flat in the air and reach the highest position. During this process, the acceleration decreases and matches the $QR$ part. After that, the foot still moves forward but starts moving downward. It speeds up, leading to an increase in acceleration, corresponding to the $RS$ part. Finally, before the foot contacts the ground, it has to slow down, and the acceleration decreases, which matches the $ST$ part. After the point $T$, there is still a part of the signal where the acceleration increases. It starts from some negative values and increases to around zero. The reason for this is, after the "heel contact" event the entire foot will eventually fully contact the ground, and the acceleration will be around zero. After the "Heel contact" event, which corresponds to the point $T$, the gait cycle enters into the stance phase, and the accelerometer value does not have too many fluctuations until the stance phase ends. At the bottom of Figure \ref{fig:accX2PQRST}, we display the matching relationship between the accelerometer signal and foot events within the gait cycle.

    \begin{figure}[!h]
    \begin{minipage}{0.49\linewidth}
    \centering
    \subfloat[Plot of accelerometer signal ("Acc\_Y") from subject 3.]{
        \label{fig:PQRSTY}
        \includegraphics[width=\linewidth]{Figures/Accelerometer2PQRST-Y.pdf}}
    \end{minipage}%
    \begin{minipage}{0.49\linewidth}
    \centering
    \subfloat[Plot of accelerometer signal ("Acc\_Z") from subject 3.]{%
        \label{fig:PQRSTZ}
          \includegraphics[width=\linewidth]{Figures/Accelerometer2PQRST-Z.pdf}%
        }
    \end{minipage}%
    \caption{\textbf{(Left):} Accelerometer signal ("Acc\_Y") plot. \textbf{(Right):} Accelerometer signal ("Acc\_Z") plot from subject 3. For each figure, the accelerometer signal plot is on the top, and one of the repetitive patterns of accelerometer signal with annotation of PQRST Complex is on the bottom. }
    \label{fig:PQRSTYZ}
    \end{figure}

    \subsubsection{Why is it called PQRST Complex?}

    As the gait cycle exists in everyone's accelerometer signal and swing phase is part of the gait cycle, the fluctuation between point $P$ and $T$ exists in everyone's gait cycle. Furthermore, in our experiment, we find that the variation of the accelerometer signal between point $P$ and $T$ varies from person to person, but the overall structure remains the same. The overall structure means that everyone has the "flat-fluctuating-flat" shape for the whole gait cycle, and the "up-down-up-down" variation pattern persists in each fluctuating part. This structure reminds us of the "P wave, QRS complex, T wave" structure in ECG. Therefore, we call this structure we captured in the accelerometer signal as "PQRST Complex". As this structure is ubiquitous in everyone's gait cycle and varies from person to person, we conjecture that this structure is unique for different people and can be used for identifying people. Our results, shown in Section \ref{sec:performance}, prove that our speculation is correct.

    The PQRST Complex contains three valleys and two peaks. As shown in the middle part of Figure \ref{fig:accX2PQRST}, they are marked with red points. From left to right, we mark $P$ (valley), $Q$ (peak), $R$ (valley), $S$ (peak), $T$ (valley) consequently. We also check if this structure exists in "Acc\_Y" and "Acc\_Z". Figure \ref{fig:PQRSTYZ} displays the plot for "Acc\_Y" and "Acc\_Z" from subject 3 on the top of each sub-figure. The zoomed repetitive patterns are shown below the accelerometer plot. We mark the PQRST Complex in each of them with red points. It shows that this structure can be captured in all three axes from accelerometer signals.

    \subsubsection{How to detect PQRST Complex?}\label{sec:howto}

    To capture the PQRST Complex, we first find the starting point $P$. According to our experiment, the point "P" is the minimum point of "Acc\_Z" in a gait cycle. In general, the length of one gait cycle varies between 800 ms - 1400 ms. Thus, the minimum point in a sliding window of 800 ms - 1400 ms is $P$. For "Acc\_X" and "Acc\_Y", the point $P$ appears a little before the point $P$ appears in "Acc\_Z". So, we find the local minima within 10 ms before the time when point $P$ of "Acc\_Z" appears to get the point $P$ in "Acc\_X" and "Acc\_Y". After finding the point $P$, we can find local maxima and local minima in turns twice, to find the following points, which are $Q$, $R$, $S$, and $T$.

    \subsection{Extracting and analyzing features in the PQRST Complex structure - Amplitude features convey more information}\label{sec:featureanalysis}

    \begin{figure*}[!ht]
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_X.]{\label{fig:AmpHistX}\includegraphics[width=\linewidth]{Figures/AmplitudeHistogramX.pdf}}
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_Y.]{%
          \includegraphics[width=\linewidth]{Figures/AmplitudeHistogramY.pdf}%
          \label{fig:AmpHistY}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_Z.]{%
          \includegraphics[width=\linewidth]{Figures/AmplitudeHistogramZ.pdf}%
          \label{fig:AmpHistZ}
        }
    \end{minipage}%
    \par\medskip
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on Acc\_X.]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramX.pdf}%
          \label{fig:IntHistX}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on .]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramY.pdf}%
          \label{fig:IntHistY}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on Acc\_Z.]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramZ.pdf}%
          \label{fig:IntHistZ}
        }
    \end{minipage}%
    \par\medskip
    \caption{Histogram plots for features from the PQRST complex. Figures in the upper row are amplitude features, and figures in the lower row are interval features. Amplitude features have wide spread of distributions. Interval features have narrow spread of distributions and are right skewed. Also, they share a large part of intersection. }
    \label{fig:Hist}
    \end{figure*}

    To describe this structure comprehensively, we define several features within the PQRST Complex in terms of amplitudes of acceleration values and time separations between foot events during the swing phase. These features are similar to the features used for ECG analysis. The amplitude of $P$ is expressed as $P_{amp}$, the amplitude of $Q$ is $Q_{amp}$, the amplitude of $R$ is $R_{amp}$, the amplitude of $S$ is $S_{amp}$ and the amplitude of $T$ is $T_{amp}$. These five amplitude features are acceleration values and unit is $m/s^2$. The interval between $P$ and $Q$ is $PQ_{inter}$, the interval between $Q$ and $R$ is $QR_{inter}$, the interval between $R$ and $S$ is $RS_{inter}$, the interval between $S$ and $T$ is $ST_{inter}$. The unit of these four interval features is millisecond. These nine features are marked in the middle figure of Figure \ref{fig:accX2PQRST}.

    We divide these nine features into two feature sets, the amplitude feature set, and the interval feature set. These three feature sets are shown as follows, and we will use these names in the rest of the paper:

    \begin{itemize}
        \item Feature set 1 (only includes five amplitude features): $P_{amp}$, $Q_{amp}$, $R_{amp}$, $S_{amp}$, $T_{amp}$.
        \item Feature set 2 (only contains four interval features): $PQ_{inter}$, $QR_{inter}$, $RS_{inter}$, $ST_{inter}$.
        \item Feature set 3 (contains all nine features): features set 1 + feature set 2.
    \end{itemize}

    Figure \ref{fig:Hist} shows the histograms of feature set 1 and feature set 2 on each axis from all subjects respectively. It is obvious that for interval features (feature set 2) on all three axes (Figure \ref{fig:IntHistX}, \ref{fig:IntHistY} and \ref{fig:IntHistZ}), the distributions are similar and largely overlapping. The distributions are not symmetric, but right skewed. Also, the spreads of the distributions are narrow, and they have a large part of intersection of each other. However, for amplitude features (feature set 1) (Figure \ref{fig:AmpHistX}, \ref{fig:AmpHistY} and \ref{fig:AmpHistZ}), features are distributed differently, centers are distinct and they do not share too many similar values. Also, the spreads of the distributions are wide, and the range for each feature is wider than interval features. It suggests that amplitude features may provide more classification information than interval features. Furthermore, features are more differently distributed on y-axis than those on the other two axes. In our experiments, we evaluate the performance of classification on these three feature sets and make a comparison among them. More details are illustrated in Section \ref{sec:exp}.

    \subsection{Importance and application of the PQRST Complex in gait analysis}

    The PQRST Complex structure is the first formally defined standard structure in gait cycles from accelerometer signals. It corresponds to the swing phase in gait cycles and captures the sequence of events during this phase. It matches the foot movement in the gait cycle, including the raising of the foot, flight of foot, and lowering of the foot. And this sequence is universal to any individual. Like the "QRS Complex" structure in ECG signals, the PQRST Complex provides a standardized structure for gait cycle representation. This structure persists in everyone's gait cycle, but its shape may vary from person to person. It leads us to a new direction of gait analysis.

    Instead of investigating the whole gait cycle, we can focus on only this PQRST Complex since it contains most of the information of the whole gait cycle with fewer points and higher efficiency. Prior studies \cite{Derawi2010Improved, gafurov2007gaitauthen, gafurov2007spoof, gafurov2006robustness, Rong2007Identification} consider the gait cycle as a whole for recognition to avoid losing structural information. They detect the whole gait cycle first and create templates from several gait cycles. This usually requires a large amount of gait data for training and many gait cycles to get reliable templates. In contrast, we create one feature vector from each PQRST Complex, and get sufficient training samples with a short amount of gait data. The above studies use distance-based or similarity-based methods to compare input samples with stored templates in the authentication process. It takes a lot of time and space to compute the distance between about 100 pairs of points \cite{derawi2012smartphones, gafurov2007gaitauthen}, which is not efficient when applied to mobile devices. However, the feature vector we extract from our PQRST Complex has only nine dimensions. We can use simple classifiers to train the dataset and get a relatively high classification accuracy. And it only takes a small amount of time and space for training and testing, which is suitable for mobile phones.

    Aggregate feature-based methods reduce the number of features used for authentication by extracting the maximum, minimum, median, etc., of the accelerometer readings. However, they miss critical structure information of the gait cycle. For instance, a gait cycle in which, the maximum appears in the first half should be different from the one in which, the maximum appears in the second half. But they are considered the same when only using maximum as features. Other aggregate features have similar issues. Thus, aggregate features are more likely to be imitated and may not appropriately represent the intricacies of the walking patterns. In contrast, our PQRST Complex focuses on the swing phase of the gait cycle, which retains as much important information as possible. At the same time, it keeps the structure information by extracting interval and amplitude features. Thus, our PQRST Complex eliminates the shortcomings of template-based methods and aggregate feature-based methods while retaining the information representing walking patterns.

    Standardization of this structure paves the way for the comparison of multiple studies and future research. For example, it matches the variations in the accelerometer signal with actual walking events. The variations in the PQRST Complex may be attributed to the muscle-skeletal structure, the pace of walking, and other factors such as the carrying of objects and wearing coats. We can use it to estimate step length and leg length, estimate velocity, and do gait cycle detection, activity detection, and carry-on items detection.

\section{Experiments}\label{sec:exp}

    \subsection{Data description and data pre-processing} \label{sec:datadescription}

    The dataset we use for this paper is a public dataset from IEEE DataPort \cite{rpaz-0h66-19}. This dataset includes several types of biometric data from 117 subjects. It contains accelerometer and gyroscope for gait, typing  for keystroke dynamics, and swiping on mobile phones. In this paper, we only use accelerometer data collected during walking tasks to test our authentication system.

    Our paper focuses on the walking pattern when people walk on flat ground, so we only use data from the following three tasks: Task 1, subjects leave the lab and walk in the corridor. Task 3, subjects walk in another corridor. Task 5, subjects walk in the first corridor again and return to the lab. Task 1 and 5 last around 20 seconds, and Task 3 lasts around 60 seconds. Subjects are asked to perform the whole walking process twice on two separate days. Data collected on the first day are called Session 1, and those collected on the second day are called Session 2. During the whole walking process, subjects are asked to put a mobile phone in the pocket of their pants, and the built-in accelerometer keeps track of the acceleration force in $m/s^2$ on x, y, and z axis, respectively, excluding the force of gravity. The frequency of the data is 100 Hz, so 100 data points represent one second.

    For data pre-processing, we first check all subjects' data and remove those with incomplete data. Then according to the checkpoints, we only retain the data for Tasks 1, 3, and 5 from the remaining dataset and remove those with less than 400 samples (equivalent to 4 seconds) in each task. Finally, 89 subjects are left. After that, we normalize the data with center 0 and standard deviation 1 using the z-score method for each axis. To remove noise, we smooth the data by using a sliding window to compute the average over the elements within each window. The length of the window is set to be 4 points.

    To construct the training and testing dataset, we use data from Session 1 for training, and data from Session 2 are used for testing. For each subject, its training and testing sets are considered genuine samples and labeled as 0, while samples from other subjects are considered imposter samples and labeled as 1.

    \begin{table*}[!t]
    \centering
    \begin{tabular}{c|c|c|c|c|c|c}
    \hline
       & \multicolumn{2}{c|}{Feature Set 1} & \multicolumn{2}{c|}{Feature Set 2}                        & \multicolumn{2}{c}{Feature Set 3}                       \\ \cline{2-7}
        & LDA      & SVM   & LDA       & SVM   & LDA      &  SVM   \\ \hline \hline
        Acc\_X & 81.26 (18.72) & 81.37 (18.61) & 74.97 (25.15) & 75.90 (24.25) & 83.48 (16.40) & 83.12 (16.79) \\ \hline
        Acc\_Y & 87.47 (12.66) & 87.70 (12.42)) & 85.00 (15.11)  & 85.33 (14.77) & 90.12 (9.97) & 90.51 (9.58) \\ \hline
        Acc\_Z & 86.74 (13.45) & 86.68 (13.45) & 80.05 (20.15) & 81.41 (18.76) & 89.43 (10.65) & 89.06 (11.02) \\ \hline
    \end{tabular}
    \caption{The average CCR and EER (numbers in the bracket) for each axis and each feature set of two classifier. All numbers are in \%. Feature Set 1 includes all five amplitude features, Feature Set 2 includes all four interval features, and Feature Set 3 includes all nine features. }
    \label{tb: results}
    \end{table*}

    \begin{table*}[h]
    \centering
    \begin{tabular}{c|c|c|c|c}
    \hline
                              & Classification methods & No. subjects & No. features        & Performance \\ \hline
    Gafurov \etal \cite{gafurov2007gaitauthen}     & Absolute distance      & 50                 & 100  & 86.3\% (CCR)  \\ \hline
    Derawi \etal \cite{Derawi2010Improved}        & DTW \& CRM             & 60                 & 100  & 5.7\% (EER)   \\ \hline
    Rong \etal \cite{Rong2007Identification}    & DTW                    & 35                 & Not mentioned             & 6.7\% (EER)   \\ \hline
    Thang \etal \cite{thang2012gait}    & DTW   & 11    & around 40     & 79.1\% (CCR) \\ \hline
    Nickel \etal \cite{nickel2012accelerometer}   & HMMs                   & 48                 & 52                        & 15.46\% (EER) \\ \hline \hline
    Our work                  & LDA,SVM                & 89                 & 9                         & 90.51\% (CCR) / 9.58\% (EER) \\ \hline
    \end{tabular}
    \caption{Performance comparison between our method and some prior studies. (DTW: Dynamic Time Warping, CRM: Cyclic rotation metric, HMMs: Hidden Markov Models)}
    \label{tb:compareResults}
    \end{table*}
    \subsection{Accelerometer-based gait authentication system using PQRST Complex}

     The authentication system first detects PQRST Complex from the training set using the method illustrated in Section \ref{sec:howto}. Then it extracts nine features and compose feature vector for each cycle.  It trains a Linear Discriminant Analysis (LDA) classifier and a Support Vector Machine (SVM) classifier separately for each pair of subjects with three feature sets, as we mentioned in Section \ref{sec:featureanalysis}. We use the Correct Classification Rate (CCR) and Equal Error Rate (EER) to evaluate the performance of our authentication system.

    \subsection{Performance evaluation and interesting observations}\label{sec:performance}

    As shown in Table \ref{tb: results}, our authentication system achieves 90.51\% CCR when using nine features with the SVM classifier, and it gets a similar performance when using the LDA classifier. It  suggests that we should include all nine features in our authentication system to make it more accurate. These results also show that even though the PQRST Complex structure only captures the swing phase of the gait cycle, it retains enough gait information for authentication and recognition.

    Table \ref{tb:compareResults} shows the performance comparison between our work and some prior studies who used gait cycles. It is worth noting that we use the least amount of features to get a relatively high CCR and low EER among these studies. At the same time, the dataset we use to evaluate our authentication system is the largest, and those two studies that achieved lower EER than ours used a much smaller dataset. These results prove that our PQRST Complex structure can capture each individual's walking patterns and be used for gait authentication. With fewer features and less computation time, our PQRST Complex can still perform reasonably well in gait authentication systems compared to prior studies. It provides a new way of accelerometer-based gait analysis except for using templates of gait cycles, aggregate features, and raw data learned by neural networks.

    Additionally, there are two interesting observations that we  find from the results.

    \textbf{Observation 1: Amplitude features perform better than interval features in classification -- }
    The Feature set 1 has better performance than the Feature set 2 (Table \ref{tb: results} column "Feature set 1" and column "Feature set 2"). This result is the same as what we conjectured in Section \ref{sec:featureanalysis}, that amplitude features are more reliable than interval features in classifying subjects due to their ranges and distributions. It implies that only using amplitude features (Feature set 1) can still achieve a relatively high CCR compared to using nine features and further reduce the computational complexity.

    \textbf{Observation 2: "Acc\_Y" and "Acc\_Z" have better performance than "Acc\_X" -- }
    It is worth noting that the performance of "Acc\_Y" and "Acc\_Z" is better than "Acc\_X". When we put the cell phone in the pants pocket, the x-axis of the accelerometer in the cell phone is along the forward direction, the y-axis of the accelerometer is vertical to the ground, and the z-axis of the accelerometer is vertical to the body. These results show that people's walking pattern is not obvious in the forward direction, while these patterns are easier to find along y and z directions.

\section{Conclusion}\label{sec:conclusion}

    In this paper, we capture a new structure PQRST Complex in gait cycles from the accelerometer signal. This structure formally matches the sequence of gait events, including raising of the foot, flight of the foot, and lowering of the foot during the swing phase in a walking cycle. It can be captured from everyone's gait cycle and varies from person to person. We posit that our PQRST Complex can become a standardized structure to represent gait cycle and opens a new area for gait analysis. Analogous to the features in ECG structure, we present nine features within PQRST Complex and use them  for recognition and authentication. We construct an accelerometer-based gait authentication system using this structure and evaluate its performance using CCR and EER. Our authentication system outperforms many state-of-the-art gait cycle-based authentication systems with an average CCR of 90.51\%, while average EER is only 9.58\%. The experimental results show that the PQRST Complex structure and features contain sufficient gait information for authentication. Compared to other studies, our authentication system not only performs well on a larger dataset, but it requires fewer features, lesser computation time and space, and shorter training data.

{\small
\bibliographystyle{ieee}

\section{Introduction}

    Gait analysis, focusing on the pattern of body movement during walking or running, has received increasing attention in recent years \cite{gafurov2007survey, wan2018survey}. There are two popular approaches used to analyze gait data. The first is video-based, which uses external cameras to record videos that directly capture body movements \cite{lee2002gait, niyogi1994analyzing}. The second is sensor-based, which analyzes signals from sensors that are attached to the human's body \cite{hou2014systemforhumangait}. Accelerometers, as a common built-in sensor in mobile devices, have become one of the most popular sensors in sensor-based gait analysis \cite{tamviruzzaman2009epetwhen}.

    Prior studies \cite{gafurov2007gaitauthen, mantyjarvi2005identifyingusers} have found that there are repetitive patterns in accelerometer signals that correspond  to two foot steps and constitute a gait cycle. These studies presented methods to detect the gait cycle, created templates or extracted features from the cycle, and matched feature vectors or templates for recognition. However, using the entire gait cycle to create templates requires much training data and a lot of computation time, which is less efficient for mobile devices. Also, aggregate gait features, such as the minimum and maximum of the whole gait cycle, cycle length, and velocity \cite{anwary2018automatic}, miss critical structural information of gait cycles. Thus, they may not represent gait information precisely and are easy to be imitated. Some studies \cite{bejarano2014novel, Maqbool2017realtime} associated "Heel contact" and "Toe off", which are two essential foot events that occur within the gait cycle, with accelerometer signals to help detect gait cycles and extract more accurate features. These two events divide the gait cycle into the stance phase, where accelerometer signals remain almost constant, and the swing phase, where accelerometer signals vary greatly. However, these studies didn't explain why these events match the points in accelerometer readings, what foot events occurred during the swing phase, and why accelerometer signals vary a lot in this period. We define a structure that consists of the swing phase, including the raising of the foot, flight of the foot, and lowering of the foot, and relate it to the changes in accelerometer signals. This structure appears in every gait cycle.

    The main contributions of this paper are as follows:
    \begin{itemize}\label{contribution}
        \item We formally define a standard structure within gait cycles from accelerometer signals, called PQRST Complex.
        It captures the most representative and persistent part of the walking patterns because the rate of change in accelerometer readings in the swing phase is very high as compared to the stance phase.
        \item We present nine features using the PQRST Complex that capture the gait cycle's change points, thus capturing variations within the cycle.
        \item We achieved an average correct classification rate (CCR)\label{abbr:CCR} of 90.51\% on an authentication system using PQRST Complex with performance better than most previous research with a smaller set of features.
    \end{itemize}

    The rest of this paper is organized as follows. Section \ref{sec:relatedwork} shows prior works in this field. In Section \ref{sec:PQRSTcomplex}, we describe the definition of the PQRST Complex and analyze features extracted from it in detail. The performance evaluation is displayed in Section \ref{sec:exp}. Finally, we conclude our work in Section \ref{sec:conclusion}.

\section{Related work}\label{sec:relatedwork}

    Signals from the accelerometer readings can be used to analyze gait \cite{ailisto2005identifying, annadhorai2008human, derawi2012smartphones}. Several methods for gait cycle detection and recognition have been proposed in the last decade. Gafurov \etal \cite{gafurov2007gaitauthen, gafurov2007spoof, gafurov2006robustness} proposed a straightforward method for gait cycle detection with an assumption that the minimas in accelerometer signals are the starting points and ending points for each gait cycle, and each cycle contains two steps. They used six consecutive cycles and used the median points of these cycles to create a feature vector and achieved a 86.3\% recognition rate. Derawi \etal \cite{Derawi2010Improved} presented an improved cycle detection method on accelerometer signals. Besides using the same assumption as Gafurov \etal \cite{gafurov2007gaitauthen}, they combined estimated cycle length (the length of one gait cycle usually varies between 800 ms - 1400 ms) and Neighbour Search to find all minimum points and utilized all detected cycles to create templates. They proposed the cyclic rotation metric (CRM)\label{abbr:CRM} to measure the distance between input samples and templates for authentication. The lowest Equal Error Rate (EER) they achieved was 5.7\%. Rong \etal \cite{Rong2007Identification} presented a gait cycle partition method and gait recognition algorithm based on Dynamic Time Warping (DTW)\label{abbr:DTW}. They used the first zero value point right after the local minimum point as the starting and ending points to separate gait cycles, and defined one gait cycle consisting of four consecutive points of zero value. They applied a time-warping network on the gait cycle they defined to create a gait feature code for each cycle, and used it for their gait recognition algorithm. They got 6.7\% EER in their recognition system. All of the methods mentioned above considered one gait cycle as a whole. They created templates from detected cycles and measured the distance between cycles from input samples and templates by using similarity-based or distance-based methods. Although they achieved relatively low EER in gait recognition or authentication, it was time-consuming to compare distance between template as each template consists of around 100 points. Moreover, none of them have given a standard structure of gait cycles. They only detected the gait cycle with starting points and end points without caring about the exact patterns that gait cycles contain.
    On the other hand, aggregate feature-based studies used features extracted from gait cycles to create feature vectors. Alobaidi \etal \cite{alobaidi2022real} extracted more than 300 features in both time domain and frequency domain, including mean, standard deviation, median, etc., of the gait cycle for activity classification. They got an average EER of 11.38\% in recognizing normal walking activity.

    As Neumann \cite{neumann2010kinesiology} illustrated in his book, human walking consists of a cyclic series of movements. In general, the gait cycle begins with the foot (heel) contacting the ground, continues as the foot (toe) leaving the ground, and ends with the same foot (heel) contacting the ground again. Thus, the beginning and end of the gait cycle are usually referred to as heel contact (HC). The toe leaving the ground separates the gait cycle into two phases: the stance phase and the swing phase. It makes these two foot events crucial for gait cycle detection. Some studies \cite{bejarano2014novel,Maqbool2017realtime} found these two events could be located in accelerometer signals to help them detect the gait cycle and estimate velocity. However, some other small foot events may also affect the changes of accelerometer signals, such as the raising of the foot, flight of the foot, and lowering of the foot during the swing phase. To the best of our knowledge, only a few studies have investigated these small events within the gait cycle. Anwary \etal \cite{anwary2021Insolebased, anwary2018automatic} found that eight foot events can be located in accelerometer signal collected from an accelerometer attached to shoes. They observed that the part where accelerometer signals vary greatly corresponds to the swing phase, and they used this observation to separate the stance and swing phases for step detection. Their results showed that this part of acceleration signal could be used to estimate the swing phase, step length, and velocity. However, they only focused on the terminal stance and toe-off events detection. They did not analyze the structure of these changes and how these foot events relate to the signal, so the gait events they separated were not accurate. In addition, accelerometer signals vary significantly in the swing phase and remain almost constant in the stance phase, and the swing phase only accounts for 40\% of the whole cycle. It suggests that it may be possible to discard 60\% of the gait cycle (stance phase) and focus on only 40\% of the gait cycle (swing phase) to improve the recognition efficiency. The structure we captured matches the swing phase. It captures the foot movements during this period, and we give an explicit explanation of why and how they are matched.

    Many accelerometer-based gait authentication systems have been proposed in recent years and got promising performance. Mufandaidza \etal \cite{mufandaidza2018continuous} developed a smartphone user authentication system using raw accelerometer data. They used the DTW algorithm to synchronize the accelerometer data from all three axes and fed them into a feed-forward neural network. The best True Positive Rate (TPR)\label{abbr:TPR} they got was 73.68\%, and the lowest False Positive Rate (FPR)\label{abbr:FPR} they got was 22.22\%. Some studies have proposed gait cycle based authentication systems. Thang \etal \cite{thang2012gait} presented two approaches for identification based on gait using accelerometer data. Their first approach extracted average gait cycles, which they called time domain features, and used DTW for comparison. The average accuracy they got was 79.1\%. Their second approach used Fast Fourier Transform (FFT) to extract frequency domain features and used Support Vector Machine (SVM) to classify feature vectors. They got an average CCR of 92.7\%. Nickel \cite{nickel2012accelerometer} constructed an accelerometer-based gait authentication on the smartphone. They came up with a cycle-based method, which used raw gait cycle data combined with some features extracted by fixed-length time interval segmentation. They used some machine learning algorithms for classification, and their methods had a low EER, which was around 6\% to 7\%.

\section{Capturing the PQRST Complex structure from accelerometer signal in gait} \label{sec:PQRSTcomplex}

\subsection{Capturing the PQRST Complex structure in accelerometer signal}

    \begin{figure}[ht]
        \centering
        \includegraphics[width=\columnwidth]{Figures/Accelerometer2PQRST2Cycle.pdf}%
        \caption{\textbf{(Top):} Accelerometer signal ("Acc\_X") plot from subject 3.  \textbf{(Middle):} One of the repetitive patterns of accelerometer signal ("Acc\_X") plot from subject 3. The PQRST Complex is captured and marked by red points. Features that we extract from this structure are also marked. \textbf{(Bottom):} Events, which one gait walking cycle includes, match the accelerometer signal. The PQRST Complex corresponds to the swing phase during the walking cycle.}
        \label{fig:accX2PQRST}
    \end{figure}

    The accelerometer has three axes, in the rest of this paper, we use "Acc\_X" to represent the data of the x-axis of the accelerometer, and "Acc\_Y" and "Acc\_Z" are used to represent the data of the y-axis and the z-axis of the accelerometer respectively. The x-axis of accelerometer signal plots are the time with unit 10 ms, and the y-axis is the acceleration value with the unit $m/s^2$.

    \subsubsection{How is PQRST Complex defined?}

   We explain the following structure on a representative subject -- subject 3 from our dataset. Figure \ref{fig:accX2PQRST} (Top) displays the plot for "Acc\_X" from subject 3. It shows repetitive patterns in the accelerometer signal. As Mantyjarvi \etal \cite{mantyjarvi2005identifyingusers} presented, these repetitive patterns represent walking cycles. To take a closer look at the structure of each walking cycle, we zoom in on one of the repetitive cycles and put it in the middle part of Figure \ref{fig:accX2PQRST}. As Anwary \etal \cite{anwary2021Insolebased} mentioned in their work, signals from the accelerometer attached to shoes are relatively steady in the stance phase when compared to the swing phase. In our study, we use accelerometer signals from phones that are placed in pants pocket. We observe that these signals also have a steady part corresponding to the stance phase and a fluctuating part corresponding to the swing phase. Figure \ref{fig:accX2PQRST} (Middle) illustrates this observation. The middle portion shows the swing phase, on which we define the PQRST complex.
    Signals before the point $P$ and after the point $T$ do not fluctuate much. It means that they match the stance phase since the foot that contacts the ground is stationary to support the body in this period. Point $P$ corresponds to the "Toe off" event. After this point, the foot starts to swing and enters the swing phase. The swing phase will end when the event "Heel contact" takes place, and the point $T$ matches this event. Since acceleration values vary a lot between $P$ and $T$, intuitively, this section of the signal would be a rich source of information for feature extraction and authentication.

    According to the variation of the acceleration values, the swing phase can be divided into several short periods. After the point $P$, the foot starts moving forward and upward, which leads to a speed up. It matches the $PQ$ part, where the acceleration increases. As the foot moves forward and upward, it will eventually become flat in the air and reach the highest position. During this process, the acceleration decreases and matches the $QR$ part. After that, the foot still moves forward but starts moving downward. It speeds up, leading to an increase in acceleration, corresponding to the $RS$ part. Finally, before the foot contacts the ground, it has to slow down, and the acceleration decreases, which matches the $ST$ part. After the point $T$, there is still a part of the signal where the acceleration increases. It starts from some negative values and increases to around zero. The reason for this is, after the "heel contact" event the entire foot will eventually fully contact the ground, and the acceleration will be around zero. After the "Heel contact" event, which corresponds to the point $T$, the gait cycle enters into the stance phase, and the accelerometer value does not have too many fluctuations until the stance phase ends. At the bottom of Figure \ref{fig:accX2PQRST}, we display the matching relationship between the accelerometer signal and foot events within the gait cycle.

    \begin{figure}[!h]
    \begin{minipage}{0.49\linewidth}
    \centering
    \subfloat[Plot of accelerometer signal ("Acc\_Y") from subject 3.]{
        \label{fig:PQRSTY}
        \includegraphics[width=\linewidth]{Figures/Accelerometer2PQRST-Y.pdf}}
    \end{minipage}%
    \begin{minipage}{0.49\linewidth}
    \centering
    \subfloat[Plot of accelerometer signal ("Acc\_Z") from subject 3.]{%
        \label{fig:PQRSTZ}
          \includegraphics[width=\linewidth]{Figures/Accelerometer2PQRST-Z.pdf}%
        }
    \end{minipage}%
    \caption{\textbf{(Left):} Accelerometer signal ("Acc\_Y") plot. \textbf{(Right):} Accelerometer signal ("Acc\_Z") plot from subject 3. For each figure, the accelerometer signal plot is on the top, and one of the repetitive patterns of accelerometer signal with annotation of PQRST Complex is on the bottom. }
    \label{fig:PQRSTYZ}
    \end{figure}

    \subsubsection{Why is it called PQRST Complex?}

    As the gait cycle exists in everyone's accelerometer signal and swing phase is part of the gait cycle, the fluctuation between point $P$ and $T$ exists in everyone's gait cycle. Furthermore, in our experiment, we find that the variation of the accelerometer signal between point $P$ and $T$ varies from person to person, but the overall structure remains the same. The overall structure means that everyone has the "flat-fluctuating-flat" shape for the whole gait cycle, and the "up-down-up-down" variation pattern persists in each fluctuating part. This structure reminds us of the "P wave, QRS complex, T wave" structure in ECG. Therefore, we call this structure we captured in the accelerometer signal as "PQRST Complex". As this structure is ubiquitous in everyone's gait cycle and varies from person to person, we conjecture that this structure is unique for different people and can be used for identifying people. Our results, shown in Section \ref{sec:performance}, prove that our speculation is correct.

    The PQRST Complex contains three valleys and two peaks. As shown in the middle part of Figure \ref{fig:accX2PQRST}, they are marked with red points. From left to right, we mark $P$ (valley), $Q$ (peak), $R$ (valley), $S$ (peak), $T$ (valley) consequently. We also check if this structure exists in "Acc\_Y" and "Acc\_Z". Figure \ref{fig:PQRSTYZ} displays the plot for "Acc\_Y" and "Acc\_Z" from subject 3 on the top of each sub-figure. The zoomed repetitive patterns are shown below the accelerometer plot. We mark the PQRST Complex in each of them with red points. It shows that this structure can be captured in all three axes from accelerometer signals.

    \subsubsection{How to detect PQRST Complex?}\label{sec:howto}

    To capture the PQRST Complex, we first find the starting point $P$. According to our experiment, the point "P" is the minimum point of "Acc\_Z" in a gait cycle. In general, the length of one gait cycle varies between 800 ms - 1400 ms. Thus, the minimum point in a sliding window of 800 ms - 1400 ms is $P$. For "Acc\_X" and "Acc\_Y", the point $P$ appears a little before the point $P$ appears in "Acc\_Z". So, we find the local minima within 10 ms before the time when point $P$ of "Acc\_Z" appears to get the point $P$ in "Acc\_X" and "Acc\_Y". After finding the point $P$, we can find local maxima and local minima in turns twice, to find the following points, which are $Q$, $R$, $S$, and $T$.

    \subsection{Extracting and analyzing features in the PQRST Complex structure - Amplitude features convey more information}\label{sec:featureanalysis}

    \begin{figure*}[!ht]
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_X.]{\label{fig:AmpHistX}\includegraphics[width=\linewidth]{Figures/AmplitudeHistogramX.pdf}}
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_Y.]{%
          \includegraphics[width=\linewidth]{Figures/AmplitudeHistogramY.pdf}%
          \label{fig:AmpHistY}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Amplitude features on Acc\_Z.]{%
          \includegraphics[width=\linewidth]{Figures/AmplitudeHistogramZ.pdf}%
          \label{fig:AmpHistZ}
        }
    \end{minipage}%
    \par\medskip
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on Acc\_X.]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramX.pdf}%
          \label{fig:IntHistX}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on .]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramY.pdf}%
          \label{fig:IntHistY}
        }
    \end{minipage}%
    \begin{minipage}{0.33\linewidth}
    \centering
    \subfloat[Interval features on Acc\_Z.]{%
          \includegraphics[width=\linewidth]{Figures/IntervalHistogramZ.pdf}%
          \label{fig:IntHistZ}
        }
    \end{minipage}%
    \par\medskip
    \caption{Histogram plots for features from the PQRST complex. Figures in the upper row are amplitude features, and figures in the lower row are interval features. Amplitude features have wide spread of distributions. Interval features have narrow spread of distributions and are right skewed. Also, they share a large part of intersection. }
    \label{fig:Hist}
    \end{figure*}

    To describe this structure comprehensively, we define several features within the PQRST Complex in terms of amplitudes of acceleration values and time separations between foot events during the swing phase. These features are similar to the features used for ECG analysis. The amplitude of $P$ is expressed as $P_{amp}$, the amplitude of $Q$ is $Q_{amp}$, the amplitude of $R$ is $R_{amp}$, the amplitude of $S$ is $S_{amp}$ and the amplitude of $T$ is $T_{amp}$. These five amplitude features are acceleration values and unit is $m/s^2$. The interval between $P$ and $Q$ is $PQ_{inter}$, the interval between $Q$ and $R$ is $QR_{inter}$, the interval between $R$ and $S$ is $RS_{inter}$, the interval between $S$ and $T$ is $ST_{inter}$. The unit of these four interval features is millisecond. These nine features are marked in the middle figure of Figure \ref{fig:accX2PQRST}.

    We divide these nine features into two feature sets, the amplitude feature set, and the interval feature set. These three feature sets are shown as follows, and we will use these names in the rest of the paper:

    \begin{itemize}
        \item Feature set 1 (only includes five amplitude features): $P_{amp}$, $Q_{amp}$, $R_{amp}$, $S_{amp}$, $T_{amp}$.
        \item Feature set 2 (only contains four interval features): $PQ_{inter}$, $QR_{inter}$, $RS_{inter}$, $ST_{inter}$.
        \item Feature set 3 (contains all nine features): features set 1 + feature set 2.
    \end{itemize}

    Figure \ref{fig:Hist} shows the histograms of feature set 1 and feature set 2 on each axis from all subjects respectively. It is obvious that for interval features (feature set 2) on all three axes (Figure \ref{fig:IntHistX}, \ref{fig:IntHistY} and \ref{fig:IntHistZ}), the distributions are similar and largely overlapping. The distributions are not symmetric, but right skewed. Also, the spreads of the distributions are narrow, and they have a large part of intersection of each other. However, for amplitude features (feature set 1) (Figure \ref{fig:AmpHistX}, \ref{fig:AmpHistY} and \ref{fig:AmpHistZ}), features are distributed differently, centers are distinct and they do not share too many similar values. Also, the spreads of the distributions are wide, and the range for each feature is wider than interval features. It suggests that amplitude features may provide more classification information than interval features. Furthermore, features are more differently distributed on y-axis than those on the other two axes. In our experiments, we evaluate the performance of classification on these three feature sets and make a comparison among them. More details are illustrated in Section \ref{sec:exp}.

    \subsection{Importance and application of the PQRST Complex in gait analysis}

    The PQRST Complex structure is the first formally defined standard structure in gait cycles from accelerometer signals. It corresponds to the swing phase in gait cycles and captures the sequence of events during this phase. It matches the foot movement in the gait cycle, including the raising of the foot, flight of foot, and lowering of the foot. And this sequence is universal to any individual. Like the "QRS Complex" structure in ECG signals, the PQRST Complex provides a standardized structure for gait cycle representation. This structure persists in everyone's gait cycle, but its shape may vary from person to person. It leads us to a new direction of gait analysis.

    Instead of investigating the whole gait cycle, we can focus on only this PQRST Complex since it contains most of the information of the whole gait cycle with fewer points and higher efficiency. Prior studies \cite{Derawi2010Improved, gafurov2007gaitauthen, gafurov2007spoof, gafurov2006robustness, Rong2007Identification} consider the gait cycle as a whole for recognition to avoid losing structural information. They detect the whole gait cycle first and create templates from several gait cycles. This usually requires a large amount of gait data for training and many gait cycles to get reliable templates. In contrast, we create one feature vector from each PQRST Complex, and get sufficient training samples with a short amount of gait data. The above studies use distance-based or similarity-based methods to compare input samples with stored templates in the authentication process. It takes a lot of time and space to compute the distance between about 100 pairs of points \cite{derawi2012smartphones, gafurov2007gaitauthen}, which is not efficient when applied to mobile devices. However, the feature vector we extract from our PQRST Complex has only nine dimensions. We can use simple classifiers to train the dataset and get a relatively high classification accuracy. And it only takes a small amount of time and space for training and testing, which is suitable for mobile phones.

    Aggregate feature-based methods reduce the number of features used for authentication by extracting the maximum, minimum, median, etc., of the accelerometer readings. However, they miss critical structure information of the gait cycle. For instance, a gait cycle in which, the maximum appears in the first half should be different from the one in which, the maximum appears in the second half. But they are considered the same when only using maximum as features. Other aggregate features have similar issues. Thus, aggregate features are more likely to be imitated and may not appropriately represent the intricacies of the walking patterns. In contrast, our PQRST Complex focuses on the swing phase of the gait cycle, which retains as much important information as possible. At the same time, it keeps the structure information by extracting interval and amplitude features. Thus, our PQRST Complex eliminates the shortcomings of template-based methods and aggregate feature-based methods while retaining the information representing walking patterns.

    Standardization of this structure paves the way for the comparison of multiple studies and future research. For example, it matches the variations in the accelerometer signal with actual walking events. The variations in the PQRST Complex may be attributed to the muscle-skeletal structure, the pace of walking, and other factors such as the carrying of objects and wearing coats. We can use it to estimate step length and leg length, estimate velocity, and do gait cycle detection, activity detection, and carry-on items detection.

\section{Experiments}\label{sec:exp}

    \subsection{Data description and data pre-processing} \label{sec:datadescription}

    The dataset we use for this paper is a public dataset from IEEE DataPort \cite{rpaz-0h66-19}. This dataset includes several types of biometric data from 117 subjects. It contains accelerometer and gyroscope for gait, typing  for keystroke dynamics, and swiping on mobile phones. In this paper, we only use accelerometer data collected during walking tasks to test our authentication system.

    Our paper focuses on the walking pattern when people walk on flat ground, so we only use data from the following three tasks: Task 1, subjects leave the lab and walk in the corridor. Task 3, subjects walk in another corridor. Task 5, subjects walk in the first corridor again and return to the lab. Task 1 and 5 last around 20 seconds, and Task 3 lasts around 60 seconds. Subjects are asked to perform the whole walking process twice on two separate days. Data collected on the first day are called Session 1, and those collected on the second day are called Session 2. During the whole walking process, subjects are asked to put a mobile phone in the pocket of their pants, and the built-in accelerometer keeps track of the acceleration force in $m/s^2$ on x, y, and z axis, respectively, excluding the force of gravity. The frequency of the data is 100 Hz, so 100 data points represent one second.

    For data pre-processing, we first check all subjects' data and remove those with incomplete data. Then according to the checkpoints, we only retain the data for Tasks 1, 3, and 5 from the remaining dataset and remove those with less than 400 samples (equivalent to 4 seconds) in each task. Finally, 89 subjects are left. After that, we normalize the data with center 0 and standard deviation 1 using the z-score method for each axis. To remove noise, we smooth the data by using a sliding window to compute the average over the elements within each window. The length of the window is set to be 4 points.

    To construct the training and testing dataset, we use data from Session 1 for training, and data from Session 2 are used for testing. For each subject, its training and testing sets are considered genuine samples and labeled as 0, while samples from other subjects are considered imposter samples and labeled as 1.

    \begin{table*}[!t]
    \centering
    \begin{tabular}{c|c|c|c|c|c|c}
    \hline
       & \multicolumn{2}{c|}{Feature Set 1} & \multicolumn{2}{c|}{Feature Set 2}                        & \multicolumn{2}{c}{Feature Set 3}                       \\ \cline{2-7}
        & LDA      & SVM   & LDA       & SVM   & LDA      &  SVM   \\ \hline \hline
        Acc\_X & 81.26 (18.72) & 81.37 (18.61) & 74.97 (25.15) & 75.90 (24.25) & 83.48 (16.40) & 83.12 (16.79) \\ \hline
        Acc\_Y & 87.47 (12.66) & 87.70 (12.42)) & 85.00 (15.11)  & 85.33 (14.77) & 90.12 (9.97) & 90.51 (9.58) \\ \hline
        Acc\_Z & 86.74 (13.45) & 86.68 (13.45) & 80.05 (20.15) & 81.41 (18.76) & 89.43 (10.65) & 89.06 (11.02) \\ \hline
    \end{tabular}
    \caption{The average CCR and EER (numbers in the bracket) for each axis and each feature set of two classifier. All numbers are in \%. Feature Set 1 includes all five amplitude features, Feature Set 2 includes all four interval features, and Feature Set 3 includes all nine features. }
    \label{tb: results}
    \end{table*}

    \begin{table*}[h]
    \centering
    \begin{tabular}{c|c|c|c|c}
    \hline
                              & Classification methods & No. subjects & No. features        & Performance \\ \hline
    Gafurov \etal \cite{gafurov2007gaitauthen}     & Absolute distance      & 50                 & 100  & 86.3\% (CCR)  \\ \hline
    Derawi \etal \cite{Derawi2010Improved}        & DTW \& CRM             & 60                 & 100  & 5.7\% (EER)   \\ \hline
    Rong \etal \cite{Rong2007Identification}    & DTW                    & 35                 & Not mentioned             & 6.7\% (EER)   \\ \hline
    Thang \etal \cite{thang2012gait}    & DTW   & 11    & around 40     & 79.1\% (CCR) \\ \hline
    Nickel \etal \cite{nickel2012accelerometer}   & HMMs                   & 48                 & 52                        & 15.46\% (EER) \\ \hline \hline
    Our work                  & LDA,SVM                & 89                 & 9                         & 90.51\% (CCR) / 9.58\% (EER) \\ \hline
    \end{tabular}
    \caption{Performance comparison between our method and some prior studies. (DTW: Dynamic Time Warping, CRM: Cyclic rotation metric, HMMs: Hidden Markov Models)}
    \label{tb:compareResults}
    \end{table*}
    \subsection{Accelerometer-based gait authentication system using PQRST Complex}

     The authentication system first detects PQRST Complex from the training set using the method illustrated in Section \ref{sec:howto}. Then it extracts nine features and compose feature vector for each cycle.  It trains a Linear Discriminant Analysis (LDA) classifier and a Support Vector Machine (SVM) classifier separately for each pair of subjects with three feature sets, as we mentioned in Section \ref{sec:featureanalysis}. We use the Correct Classification Rate (CCR) and Equal Error Rate (EER) to evaluate the performance of our authentication system.

    \subsection{Performance evaluation and interesting observations}\label{sec:performance}

    As shown in Table \ref{tb: results}, our authentication system achieves 90.51\% CCR when using nine features with the SVM classifier, and it gets a similar performance when using the LDA classifier. It  suggests that we should include all nine features in our authentication system to make it more accurate. These results also show that even though the PQRST Complex structure only captures the swing phase of the gait cycle, it retains enough gait information for authentication and recognition.

    Table \ref{tb:compareResults} shows the performance comparison between our work and some prior studies who used gait cycles. It is worth noting that we use the least amount of features to get a relatively high CCR and low EER among these studies. At the same time, the dataset we use to evaluate our authentication system is the largest, and those two studies that achieved lower EER than ours used a much smaller dataset. These results prove that our PQRST Complex structure can capture each individual's walking patterns and be used for gait authentication. With fewer features and less computation time, our PQRST Complex can still perform reasonably well in gait authentication systems compared to prior studies. It provides a new way of accelerometer-based gait analysis except for using templates of gait cycles, aggregate features, and raw data learned by neural networks.

    Additionally, there are two interesting observations that we  find from the results.

    \textbf{Observation 1: Amplitude features perform better than interval features in classification -- }
    The Feature set 1 has better performance than the Feature set 2 (Table \ref{tb: results} column "Feature set 1" and column "Feature set 2"). This result is the same as what we conjectured in Section \ref{sec:featureanalysis}, that amplitude features are more reliable than interval features in classifying subjects due to their ranges and distributions. It implies that only using amplitude features (Feature set 1) can still achieve a relatively high CCR compared to using nine features and further reduce the computational complexity.

    \textbf{Observation 2: "Acc\_Y" and "Acc\_Z" have better performance than "Acc\_X" -- }
    It is worth noting that the performance of "Acc\_Y" and "Acc\_Z" is better than "Acc\_X". When we put the cell phone in the pants pocket, the x-axis of the accelerometer in the cell phone is along the forward direction, the y-axis of the accelerometer is vertical to the ground, and the z-axis of the accelerometer is vertical to the body. These results show that people's walking pattern is not obvious in the forward direction, while these patterns are easier to find along y and z directions.

\section{Conclusion}\label{sec:conclusion}

    In this paper, we capture a new structure PQRST Complex in gait cycles from the accelerometer signal. This structure formally matches the sequence of gait events, including raising of the foot, flight of the foot, and lowering of the foot during the swing phase in a walking cycle. It can be captured from everyone's gait cycle and varies from person to person. We posit that our PQRST Complex can become a standardized structure to represent gait cycle and opens a new area for gait analysis. Analogous to the features in ECG structure, we present nine features within PQRST Complex and use them  for recognition and authentication. We construct an accelerometer-based gait authentication system using this structure and evaluate its performance using CCR and EER. Our authentication system outperforms many state-of-the-art gait cycle-based authentication systems with an average CCR of 90.51\%, while average EER is only 9.58\%. The experimental results show that the PQRST Complex structure and features contain sufficient gait information for authentication. Compared to other studies, our authentication system not only performs well on a larger dataset, but it requires fewer features, lesser computation time and space, and shorter training data.

{\small
\bibliographystyle{ieee}


\section{Introduction}

Hilbert $C^*$-modules were introduced by W. Paschke in \cite{Pas1} and became a useful tool in
various aspects of noncommutative geometry and topology. The idea behind this notion is
to generalize the notion of a Hilbert space by replacing the field of the complex numbers,
both as scalars and as the range for the inner product, by a $C^*$-algebra $A$. For details about
Hilbert $C^*$-modules we refer to \cite{Lance,MTBook,MT}. In some aspects, Hilbert $C^*$-modules behave
like Hilbert spaces, but there are three major differences.

First, while any element $m\in M$ of a Hilbert $C^*$-module $M$ determines an $A$-antilinear
map $x\mapsto \langle x,m\rangle = \widehat m(x)$, $\widehat m : M \to A$, not any bounded $A$-antilinear map from $M$ to $A$ is
of this form, i.e. there is no Riesz theorem. The $A$-module of all bounded $A$-antilinear maps
is called the dual module and is denoted by $M'$. The map $m\mapsto \widehat m$ determines an isometric
inclusion $M\subset M'$, which is often not surjective. As a corollary, bounded $A$-linear operators
on Hilbert $C^*$-modules need not have an adjoint. This explains the interest in special classes
of Hilbert $C^*$-modules like self-dual or reflexive ones.

The dual module $M'$ often has no Hilbert $C^*$-module structure. Nevertheless, when the
underlying $C^*$-algebra $A$ is a $W^*$-algebra, or, slightly more generally, a monotone complete
$C^*$-algebra, the inner product $\langle\cdot,\cdot\rangle$ extends from $M$ to $M'$ in a natural way, \cite{F_1995}.

Second, while there is only one (up to an isometric isomorphism) separable Hilbert space
$l_2(\mathbb C)$, a countably generated Hilbert $C^*$-module over $A$ need not be isometrically isomorphic
to the standard Hilbert $C^*$-module $l_2(A)$.

Third, a Hilbert $C^*$-submodule $M\subset N$ in a Hilbert $C^*$-module $N$ need not be (orthogonally)
complementable. It may easily happen that the orthogonal complement $M^\perp$ is zero,
while $M$ is strictly smaller than $N$. We call such submodules {\it thick}.

Any element $n\subset N$ determines a functional $\widehat n|_M$ on $M$ given by $\widehat n|_M(m)=\langle m, n\rangle$. A
long-standing problem was to check whether the norms $\|n\|$ and $\|\widehat n|_M\|$ coincide. If $A$ is a
$W^*$-algebra and if $N=M'$ (in this case $M'$ is a Hilbert $C^*$-module) then it was shown in
\cite{Pas1} that these two norms are the same.

Recently, a surprising counterexample appeared in \cite{KS}, showing that for $A=C[0; 1]$ and
for $M=l_2(A)$, there exists $N$ such that $M$ is thick in $N$, and the two norms differ. As
a concequence, it was shown in \cite{KS} that there exist non-zero functionals on $N$ with zero
restriction onto $M$, thus showing that thick submodules may be not so thick.

Hilbert $C^*$-modules over $C[0,1]$ are reflexive, i.e. the second dual module $M''$ coincides with $M$, but the first dual module is not a Hilbert one, which is a reason behind a lot of counterexamples. In this paper, we focus on the class of Hilbert $C^*$-modules, for which $M'=M''$ is a Hilbert $C^*$-module. In particular, this is the case when $A$ is a monotone complete $C^*$-algebra \cite{F_1995}.

We show that even when $A$ is monotone complete, the two norms may be different. On the other hand, we show that if $A=L^\infty(X)$ is a commutative $W^*$-algebra or $A=\mathbb B(H)$ is the algebra of all bounded operators on a Hilbert
space then the two norms coincide. We have no idea on what happens when $A$ is a general
$W^*$-algebra.

In order to compare the norms, we associate to each element $f$ of the dual module, a right
ideal $J_f$ in $A$ and show that the size of this ideal is related to the coincidence of the two
norms.

The author is grateful to M. Frank and E. Troitsky for fruitful discussions.

\section{Hilbert $C^*$-modules with Hilbert dual}

Recall that the map $m\mapsto \widehat m$, $M\to M'$, defines an isometric inclusion, so we may identify $M$ with a subset in $M'$ via this map.

\begin{dfn}
A Hilbert $C^*$-module $M$ over a $C^*$-algebra $A$ is called a \textit{module with a Hilbert dual} if the inner product $\langle\cdot,\cdot\rangle$ on $M$ extends to an inner product $\langle\cdot,\cdot\rangle'$ on $M'$ such that $\langle \widehat m,\widehat n\rangle'=\langle m,n\rangle$ and $f(m)=\langle \widehat m,f\rangle'$ for any $m,n\in M$ and any $f\in M'$.

\end{dfn}

\begin{lem}
Let $M$ be a Hilbert $C^*$-module with a Hilbert dual. Then $M'$ is self-dual.

\end{lem}
\begin{proof}
The identity map extends to the inclusion $M''\subset M'$ for any Hilbert $C^*$-module. If $M'$ is a Hilbert $C^*$-module then the identity map extends to the inclusion $M'\subset M''$. Hence $M''=M'$.

\end{proof}

\begin{prop}
Let $\langle\cdot,\cdot\rangle'$ and $\langle\cdot,\cdot\rangle''$ be two such extensions of the inner product on $M$ to inner products on $M'$. Then they coincide.

\end{prop}
\begin{proof}

Set $\langle f,g\rangle^+=\frac{1}{2}(\langle f,g\rangle'+\langle f,g\rangle'')$, $f,g\in M'$. Then $\langle\cdot,\cdot\rangle^+$ is also an extension of the inner product on $M$. Then $\langle f,f\rangle'\leq 2\langle f,f\rangle^+$ for any $f\in M'$, hence $\id:M'\to M'$ is a bounded map from $(M',\langle,\cdot,\cdot\rangle^+)$ to $(M',\langle,\cdot,\cdot\rangle')$. It is also obviously $A$-linear.

As $M'$ with any inner product is self-dual, there exists the adjoint operator $\id^*:(M',\langle,\cdot,\cdot\rangle')\to (M',\langle,\cdot,\cdot\rangle^+)$. By definition, $\langle \id f,g\rangle'=\langle f,\id^*g\rangle^+$ for any $f,g\in M'$. In particular, this holds for $f=\widehat m$, $m\in M$. Then
$$
\langle \id \widehat m,g\rangle^+=\langle \widehat m,g\rangle=\langle \widehat m,\id^* g\rangle=\langle \widehat m,\id^* g \rangle'
$$
for any $g\in M'$ and any $m\in M$, hence $\id^*g=\id g$, i.e. $\id^*=\id$, therefore $\langle f,g\rangle'=\langle \id f,\id g\rangle^+$ for any $f,g\in M'$. Thus, $\langle f,g\rangle'=\langle f,g\rangle''$ for any $f,g\in M'$.

\end{proof}

Any self-dual Hilbert $C^*$-module and any Hilbert $C^*$-module over a monotone complete $C^*$-algebra is obviously a module with a Hilbert dual \cite{F_1995}.

\section{Right ideals from functionals}

Let $f\in M'$. Define the subset $J_f\subset A$ by $J_f=\{a\in A:fa\in M\}$.
\begin{lem}
$J_f$ is a closed right ideal in $A$.

\end{lem}
\begin{proof}
Obvious.
\end{proof}

Apart from the trivial case when $f\in M$ (then $M_f=A$), there are two extreme cases for the right ideal $J_f$ when $f\notin M$:
\begin{itemize}
\item
$J_f$ is zero;
\item
$J_f$ is essential, i.e. $aJ_f=0$, $a\in A$, implies $a=0$.
\end{itemize}

Let $M$ be a Hilbert $C^*$-module over a $C^*$-algebra $A$, $f\in M'$. Define $M^0_f$ as the $A$-linear span of $M$ and $f$, i.e.
$$
M^0_f=\{m+fa:m\in M,a\in A\}\subset M',
$$
and let $M_f$ be the norm closure of $M^0_f$. Usually, $M_f$ need not be a pre-Hilbert $C^*$-module, i.e. the inner product on $M$ need not be extendable to $M_f$, but sometimes this happens, e.g. when $A$ is a monotone complete $C^*$-algebra \cite{F_1995}. We are interested in the uniqueness of the inner product extension from $M$ to $M_f$, or to larger modules, e.g. to $M'$.

\begin{lem}
Suppose that the inner product on $M$ extends to an inner product on $M_f$. If the right ideal $J_f$ is essential then the extended inner product on $M_f$ is unique.

\end{lem}
\begin{proof}
Let $\langle\cdot,\cdot\rangle_1$ and $\langle\cdot,\cdot\rangle_2$ be two extensions of the inner product $\langle\cdot,\cdot\rangle$ on $M$ making $M_f$ a pre-Hilbert $C^*$-module. Set $a_i=\langle f,f\rangle_i$, $i=1,2$. If $j\in J_f$ then $fj\in M$, hence $f(fj)=\langle fj,f\rangle_i$, $i=1,2$, hence $j^*a_1=j^*a_2$, or, equivalently, passing to the adjoints, $(a_2-a_1)j=0$. As this holds for any $j\in J_f$ and as $J_f$ is essential then $a_2-a_1=0$, hence the two inner products coincide.

\end{proof}

\begin{thm}\label{=}
Suppose that $M$ is a Hilbert $C^*$-module with a Hilbert dual, and let $\langle\cdot,\cdot\rangle_{M'}$ be the extention of the inner product $\langle\cdot,\cdot\rangle$ from $M$ to $M'$. Suppose also that $M$ is a thick submodule in a Hilbert $C^*$-module $N$ with the inner product $\langle\cdot,\cdot\rangle_N$, which determines an injection $i:N\to M'$ (the inner product on $M$ is supposed to be the restriction of the inner product on $N$). If the right ideal $J_f$ is essential for any $f\in M'$ then the inner product on $N$ coincides with the extended inner product on $M'$, i.e. $\langle n,n'\rangle_N=\langle i(n),i(n')\rangle_{M'}$ for any $n,n'\in N$.

\end{thm}
\begin{proof}
Recall that the injection $j$ is defined as follows: for $n\in N$, set $i(n)(m)=\langle m,n\rangle_N$, $m\in M$, i.e. $i(n)=\widehat n|_M$. Thickness of $M$ in $N$ implies that $i$ is injective.

Suppose that there exists $n\in N$ such that $\langle n,n\rangle_N\neq\langle i(n),i(n)\rangle_{M'}$. Set $f=i(n)\in M'$, and let $j\in J_f$. Then, by definition, $m=i(n)j\in M$, and
$$
\langle m',nj\rangle_N=\langle m',nj\rangle_N=i(nj)(m')=\langle m',i(n)j\rangle_{M'},\quad m'\in M
$$
hence $\langle m',nj-m\rangle_N=0$ for any $m'\in M$. As $M$ is thick in $N$, the latter implies that $nj=m\in M$.

Set $a=\langle n,n\rangle_N$, $b=\langle i(n),i(n)\rangle_{M'}$. Then
$$
j^*aj=\langle nj,nj\rangle_N=\langle m,m\rangle_M=\langle i(n)j,i(n)j\rangle_{M'}=j^*bj,
$$
hence $j^*(a-b)j=0$ for any $j\in J_f$. As $J_f$ is essential, this implies that $a=b$. Thus, $\langle n,n\rangle_N=\langle i(n),i(n)\rangle_{M'}$ for any $n\in N$. Polarization identity then implies that $\langle n',n\rangle_N=\langle i(n'),i(n)\rangle_{M'}$ for any $n,n'\in N$.

\end{proof}

\begin{thm}\label{neq}
Suppose that $m$ is a Hilbert $C^*$-module with a Hilbert dual, and let $\langle\cdot,\cdot\rangle'$ be the extension of the inner product $\langle\cdot,\cdot\rangle$ from $M$ to $M'$, hence to $M_f\subset M'$.
Suppose also that $\langle f,f\rangle'\geq 1$.
If $J_f=0$ then there exists a Hilbert $C^*$-module $N$ such that $M\subset N$ is thick, $f\in N$, and the norm of $f$ as a functional (i.e. the standard norm on $M'$) is strictly smaller than the norm of $f$ as an element of $N$.

\end{thm}
\begin{proof}
 The condition $J_f=0$ means that the subspaces $M$ and $fA=\{fa:a\in A\}$ form a direct sum (note that it need not be a topological direct sum) equal to $M^0_f$. Let $c=\langle f,f\rangle'\in A$, and, for $m+fa,m'+fa'\in M^0_f$, set
$$
\langle m+fa,m'+fa'\rangle_+=\langle m+fa,m'+fa'\rangle'+a^*c a'.
$$

Let us check linearity with respect to the first argument:
\begin{eqnarray*}
\langle m_1{+}m_2{+}f(a_1{+}a_2),m'{+}fa'\rangle_{+}&\!=\!&\langle m_1{+}m_2{+}f(a_1{+}a_2),m'{+}fa'\rangle'{+}(a_1{+}a_2)ca'\\
&\!=\!&
\langle m_1{+}fa_1,m'{+}fa'\rangle'{+}\langle m_2{+}fa_2,m'{+}fa'\rangle'{+}(a_1{+}a_2)ca'\\
&\!=\!&
\langle m_1{+}fa_1,m'{+}fa'\rangle_{+}{+}\langle m_2{+}fa_2,m'{+}fa'\rangle_{+}.
\end{eqnarray*}
Other properties of an inner product obviously hold, making thus $M^0_f$ a pre-Hilbert $C^*$-module with respect to $\langle\cdot,\cdot\rangle_+$.

Let us show that $M^0_f$ is complete with respect to the norm $\|\cdot\|_+$ determined by the inner product $\langle\cdot,\cdot\rangle_+$ (it may be not complete with respect to the norm on $M'$).

Suppose that $\{m_k+fa_k\}_{k\in\mathbb N}$ is a Cauchy sequence with respect to $\|\cdot\|_+$, where $m_k\in M$, $a_k\in A$, $k\in\mathbb N$. Note that $\|fa\|_+\leq\|m+fa\|_+$ for any $m\in M$, $a\in A$, therefore, $\{fa_k\}_{k\in\mathbb N}$ is a Cauchy sequence as well. Then $\{m_k\}_{k\in\mathbb N}$ is Cauchy too.

As $\langle f,f\rangle'\geq 1$, we have
$$
a^*a\leq a^*\langle f,f\rangle'a=\langle fa,fa\rangle'
$$
for any $a\in A$, hence
$$
\|a_k-a_n\|^2\leq \langle fa_k-fa_n,fa_k-fa_n\rangle',
$$
so $\{ak\}_{k\in\mathbb N}$ is a Cauchy sequence too. As both $A$ and $M$ are complete, the limit of the
sequence $\{m_k + fa_k\}_{k\in\mathbb N}$ is of the form $m + fa$ for some $m\in M$ and $a\in A$, thus $M^0_
f$ is complete.

Note that
$$
\langle m,m'+fa\rangle_+=\langle m,m'+fa\rangle'=\langle m,m'\rangle+f(m)a,\quad m,m'\in M, a\in A,
$$
hence $\langle\cdot,\cdot\rangle_+$ is an extension of the inner product $\langle,\cdot,\cdot\rangle$ on $M$ to $N$.
As $M$ is thick in $M'$, it is thick in $N$ as well. Indeed, if $\langle m,m'+fa\rangle_+=0$ for any $m\in M$ then
$\langle m,m'+fa\rangle'=0$, hence $m'+fa\in M'$ is orthogonal to the whole $M$, hence $m'+fa=0$.

Finally,
$$
\|f\|'=(\langle f,f\rangle')^{1/2}=\|c\|^{1/2},
$$
while
$$
\|f\|_+=(\langle f,f\rangle_+)^{1/2}=(\langle f,f\rangle'+c)^{1/2}=\sqrt{2}\|c\|^{1/2}.
$$

\end{proof}

\begin{rmk}
Considering $\widetilde M=A\oplus M$ instead of $M$, and $\widetilde f = (\widehat 1_A, f)\in \widetilde M'$ instead of
$f\in M'$, we get $\langle \widetilde f, \widetilde f\rangle'\geq 1$, and $J_{\widetilde f}=J_f$, so the condition $\langle f,f\rangle'\geq 1$ is not restrictive.

\end{rmk}

\section{Positive results}

For a Hilbert $C^*$-module $N$ we write $\widehat n$ for the functional $x\mapsto\langle n,x\rangle$.

\begin{thm}
Let $M\subset N$ be Hilbert $C^*$-modules over a commutative $W^*$-algebra $A=C(X)$ such that $M$ is countably generated and $M^\perp=0$. Then $\|n\|=\|\widehat n|_M\|$ for any $n\in N$,i.e. the map $n\mapsto\widehat n|_M$, $N\to M'$, is an isometry.

\end{thm}
\begin{proof}
If $M$ is countably generated then it can be considered as a direct summand in the standard Hilbert $C^*$-module $l_2(A)$, i.e. $l_2(A)=M\oplus K$ for some Hilbert $C^*$-module $K$. The functional $\widehat n|_M$, $n\in N$, can be similarly considered as a functional on $l_2(A)$ (defined by zero on $K$). If $\|n\|\neq\|\widehat n|_M\|$ for some $n\in N$ then the two norms differ for $(n,0)\in N\oplus K$, so the proof reduces to the case when $M=l_2(A)$.

Let $f\in M'$, and let $J_f=\{a\in A: fa\in M\}$ be an ideal in $A$. We claim that if $M=l_2(A)$ then $J_f$ is essential for any $f\in M'$, i.e. $aJ_f=0$, $a\in A$, implies that $a=0$. Let $f=(f_n)_{n\in\mathbb N}$, $f_n\in C(X)$. The condition $f\in M'$ means that $\sum_{n=1}^\infty |f_n|^2$ is bounded. Set $g_n=\sum_{k=1}^n|f_n|^2$. As $A$ is a $W^*$-algebra, the least upper bound $\bar g$ of the monotone sequence $(g_n)_{n\in\mathbb N}$ exists and coincides with the pointwise limit
$\check g=\lim_{n\to\infty}g_n$
outside a meager subset $Y_f$ of $X$. We claim that $J_f$ consists of all functions $a$ vanishing on $Y_f$. Recall that $fa\in M$ iff the sequence $\{f_na\}_{n\in\mathbb N}$ is norm convergent.

Supppose that $a\in A$, $a|_{Y_f}=0$. Given $\varepsilon>0$, set $U=\{x\in X:|a(x)|<\frac{\varepsilon}{\|\bar g\|}\}$.
Clearly, $U\subset X$ is open, and $Y_f\subset U$. Then $|g_n(x)a(x)-\bar{g}(x)a(x)|\leq\varepsilon$ for any $x\in U$ and for
any $n\in\mathbb N$. On the compact set $X\setminus U$, the sequence $\{g_na\}_{n\in\mathbb N}$ converges pointwise to the
continuous function $\bar g a$, hence the convergence is uniform --- both on $U$ and on $X\setminus U$. Thus,
$a\in J_f$.

Now, let $a\in J_f$. Suppose that there exists $x_0\in Y_f$ such that $a(x_0)\neq 0$. The sequence
$\{g_na\}_{n\in\mathbb N}$ is uniformly convergent on $X$, hence $\check ga$ is continuous and coincides with $\bar ga$, i.e.
$\bar g(x)a(x)=\check g(x)a(x)$ for any $x\in X$. But $\bar g(x_0)\neq \check g(x_0)$. This contradiction shows that
$a|_{Y_f}=0$.

Let us show that the ideal $J_f$ is essential. Let $aJ_f=0$ for some $a\in C(X)$. Let $V=\{x\in X:a(x)\neq 0\}$. Then $V$ is an open subset of $X$. As $ab=0$ for any $b\in J_f$, we should have $b(x)=0$ for any $x\in V$. Recall that if $C(X)$ is a $W^*$-algebra then $X$ is a hyperstonean space. By Corollary following Proposition 5 of \cite{Dixmier}, in hyperstonean spaces, any meager set is nowhere dense, i.e. the interior of its closure is empty. Recall that functions in $J_f$ equal zero on $Y_f$, hence, on its closure $\overline{Y}_f$. The condition $aJ_f=0$ means that for any $b\in J_f$ one has
$b|_V=0$. We claim that this implies $V\subset \overline{Y}_f$. Indeed, assume the contrary: let $x_0\in V\setminus\overline{Y}_f$ satisfy the condition: any continuous function that vanishes on $\overline{Y}_f$ vanishes at $x_0$. As $X$ is
compact and Hausdorff, it is normal, hence there exists a continuous function that vanishes
on $\overline{Y}_f$ and equals 1 at $x_0$. This contradiction proves $V\subset\overline{Y}_f$. But $Y_f$ is nowhere dense,
hence the open set $V$ must be empty. Hence $a=0$.

\end{proof}

Let $J$ be of $c_0$-$\sum_{i}\oplus \mathbb K(H_i)$-type, i.e. it has a faithful $*$-representation as a $C^*$-algebra of compact operators on some Hilbert space, and let $A\supset J$ be a $C^*$-algebra such that $J$ is an essential ideal in $A$. As examples, we may consider $A=\mathbb B(H)$, $J=\mathbb K(H)$ and $A=l_\infty$, $J=c_0$.

\begin{thm}
Let $M\subset N$ be Hilbert $C^*$-modules over $A$ such that $M^\perp=0$. Suppose that $M$ is a Hilbert $C^*$-module with a Hilbert dual. If $A$ is a $C^*$-algebra containing an essential ideal $J$ of $c_0$-$\sum_{i}\oplus \mathbb K(H_i)$-type then $\|n\|=\|\widehat n|_M\|$ for any $n\in N$, i.e. the map $n\mapsto\widehat n|_M$, $N\to M'$, is an isometry.

\end{thm}
\begin{proof}
Denote by $MJ\subset M$ the norm closure of the linear span of $\{mj:m\in M,j\in J\}$. Then $MJ$ is a Hilbert $C^*$-module over $J$. Clearly, $MJ\subset NJ$. It was shown in \cite{Magajna} that any submodule over $J$ is orthogonally complemented.

We claim that $MJ=NJ$. Indeed, if this is not true then  the orthogonal complement for $MJ$ in $NJ$ is not zero. Let $x\in NJ$ satisfy $x\perp MJ$. Then $\langle mj,x\rangle=0$ for any $m\in M$ and any $j\in J$. As $J$ is essential, we can conclude that $\langle m,x\rangle=0$ for any $m\in M$. As $M^\perp=0$ in $N$, we conclude that $x=0$.
It follows that $nj\in M$ for any $n\in N$ and any $j\in J$.

Similarly, consider the inclusion $M\subset M'$. Here we have $M^\perp=0$ as well. Passing to $MJ\subset M'J$, we can conclude that $fj\in M$ for any $f\in M'$. In particular, $\widehat n|_M\cdot j\in M$.

By assumption, $M'$ is a Hilbert $C^*$-module with the inner product $\langle\cdot,\cdot\rangle_{M'}$. By Theorem \ref{=},
$\langle \widehat n|_M,\widehat n|_M\rangle_{M'}=\langle n,n\rangle_N$ for any $n\in N$.

\end{proof}

\section{Negative results}

Here we show that the norm of extensions of functionals from thick submodules may be not unique even for commutative monotone complete $C^*$-algebras. Take $X=[0,1]$, and consider the $C^*$-algebra $Bor(X)$ of all bounded Borel functions with the sup-norm. Consider the set $J$ of all functions $a\in Bor(X)$ such that the set $\{x\in X:a(x)\neq 0\}$ is meager. The set $J$ is an ideal in $Bor(X)$, so let $A=B(X)=Bor(X)/J$ be the quotient $C^*$-algebra. We
denote the equivalence class of $a$ by $[a]\in A$.
The $C^*$-algebra $B(X)$ was showed to be monotone complete in \cite{Dixmier}, while $Bor(X)$ is only monotone $\sigma$-complete \cite{S-W}.

\begin{lem}\label{Borel}
There exists $f\in l_2(A)'$ with $\langle f,f\rangle'\geq 1$ such that $fa\in l_2(A)$ for $a\in A$ implies that $a=0$.

\end{lem}
\begin{proof}
We use the idea from \cite{KS} to construct $f=([f_1],[f_2],\ldots)\in l_2(A)'$ in such a way that the least upper bound for the partial sums of $\sum_{k=1}^\infty |f_k|^2$ would differ from their pointwise limit on the set of rationals in $(0,1)$. Here $f_k\in Bor(X)$, $k\in\mathbb N$.

Let $(r_m)_{m\in\mathbb N}$ be the sequence of all rational numbers in $(0,1)$ enumerated by natural numbers. For each $r_m$, take a strictly increasing sequence $\alpha_m^k\in(0,1)$ such that $\lim_{k\to\infty}\alpha_m^k=r_m$, and let $h_m^k$ be the characteristic function of the interval $[\alpha_m^k,\alpha_m^{k+1})$. Fix a bijection
$$
\varphi:\mathbb N\to\mathbb N^2,\quad \varphi(n)=(m(n),k(n)),
$$
and set $f_n=\frac{1}{2^{m(n)}}h_{m(n)}^{k(n)}$. Then the partial sums $\sum_{n=1}^N |f_n|^2$ (and hence $\sum_{n=1}^N [|f_n|]^2$) are uniformly bounded, hence $f=([f_n])_{n\in\mathbb N}\in l_2(A)'$. Note that we could take continuous functions instead of $h_n^k$ to get a required $f$. To fit the condition $\langle f,f\rangle'\geq 1$ we may replace the constructed $f=([f_1],[f_2],\ldots)$ by $(1_A,[f_1],[f_2],\ldots)$. For shortness' sake set $g_m=\sum_{k=1}^m|f_k|^2\in Bor(X)$.

The series $\sum_{k=1}^n[|f_k|]^2$ is not norm convergent in $B(X)$ (i.e. $f\notin l_2(A)$). Indeed, note first that $\|\chi\|_{Bor(X)}=\|[\chi]\|_{B(X)}=1$ for a characteristic function $\chi$ of any open subset of $X$. The norm in the quotient algebra is given by
$$
\|[\chi]\|_{B(X)}=\inf_{\psi\in J}\|\chi+\psi\|_{Bor(X)}=1
$$
as $\psi$ vanishes outside of a meager set. Take any $N\in\mathbb N$. There exists $n_0\in\mathbb N$ such that $m(N+n_0)=1$. Then, for any $M>N+n_0$, we have $g_M-g_N\geq\frac{1}{2}h_1^{k(N+n_0)}$, hence
$$
\|[g_M]-[g_N]\|\geq\frac{1}{2}\|[h_1^{k(N+n_0)}]\|=\frac{1}{2}.
$$

Moreover, this series is not norm convergent on any closed interval $[c,d]=V\subset X$. Let $\check q:Bor(X)\to Bor(V)$ denote the restriction map. It induces the map of the quotients $q:B(X)\to B(V)$. We claim that the series $\sum_{k=1}^\infty q([|f_k|])^2$ is not norm convergent. Indeed, take $m_0$ such that $r_{m_0}\in V$, then we can repeat the previous argument.
For any $N\in\mathbb N$ we can find $n_0\in\mathbb N$ such that $m(N+n_0)=m_0$. Then, for any $M>N+n_0$, we have $g_M-g_N\geq\frac{1}{2^{m_0}}h_{m_0}^{k(N+n_0)}$, hence
$$
\|[g_M]-[g_N]\|\geq\frac{1}{2^{m_0}}\|[h_{m_0}^{k(N+n_0)}]\|=\frac{1}{2^{m_0}}.
$$

Let $a\in B(X)$ such that $a\neq 0$ and $fa\in l_2(A)$. Set $b=aa^*$, then $b\neq 0$, $b\geq 0$ and $fb\in l_2(A)$, so we may replace $a$ by $b$. If we show that $b=0$ then $a=0$ as well.

Recall that every equivalence class in $B(X)$ has a lower semicontinuous representative \cite{Dixmier},
so there exists a lower semicontinuous $\beta\in Bor(X)$ such that $[\beta]=b$. Let
$$
f(t)=\left\lbrace\begin{array}{cl}t&\mbox{if\ }t\geq 0;\\0&\mbox{if\ }t<0.\end{array}\right.
$$
Then $[f\circ\beta]=f([\beta])=f(b)=b$. As $f$ is non-decreasing, it is easy to see that $\alpha=f\circ\beta\in Bor(X)$ is also lower semicontinuous. We also have $\alpha(x)\geq 0$ for any $x\in X$.
As $b\neq 0$, there exists $\varepsilon>0$ and a non-empty open set $U\subset X$
such that $\alpha(x)>\varepsilon$ for any $x\in U$. Let $V\subset U$ be a non-empty closed subset. If the sequence $\{[g_n]b\}_{n\in\mathbb N}$ is norm convergent in $B(X)$ (i.e. if $fb\in l_2(A)$) then the sequence $\{q([g_n])\}_{n\in\mathbb N}$ is norm convergent in $B(V)$ too  --- a contradiction.

\end{proof}

\begin{cor}
There exists a monotone complete commutative $C^*$-algebra $A$, a Hilbert $C^*$-module $N$ over $A$, a thick submodule $M\subset N$, and $n\in N$ such that $\|n\|_N>\|\widehat n|_M\|_{M'}$.

\end{cor}
\begin{proof}
Let $A$ be as above, $M=l_2(A)$. Take $f\in l_2(A)'$ as in Lemma \ref{Borel}, i.e. such that $J_f=0$.
Then apply Theorem \ref{neq}.

\end{proof}

There is an interesting consequence of this result. We show that there exist functionals in $N'$ that equal zero on $M$.

Let $M\subset N$, and suppose that both $M$ and $N$ are Hilbert $C^*$-modules with a Hilbert dual.
Denote the inclusion $M\to N$ by $\alpha$, and define the map $P:N'\to M'$ by $P(g)(m)=g(\alpha(m))$, $g\in N'$, $m\in M$. As the dual modules are Hilbert $C^*$-modules, this can be written as
\begin{equation}\label{1}
\langle \widehat m,P(g)\rangle_{M'}=\langle \widehat{\alpha(m)},g\rangle_{N'}.
\end{equation}

As the dual modules are Hilbert $C^*$-modules, they are self-dual, i.e. equal to their second duals. Therefore, all bounded operators are adjointable. Let $I=P^*:M'\to N'$. Then $\langle f,P(g)\rangle_{M'}=\langle I(f),g\rangle_{N'}$, $f\in M'$. Taking $f=\widehat m$, $m\in M$, we get
\begin{equation}\label{2}
\langle \widehat m,P(g)\rangle_{M'}=\langle I(\widehat m),g\rangle_{N'}.
\end{equation}

Comparing (\ref{1}) and (\ref{2}), we see that $I(\widehat m)=\widehat{\alpha(m)}$ for any $m\in M$.

\begin{thm}\label{Thm}
Let $M\subset N$ be a thick submodule, let both $M$ and $N$ are Hilbert $C^*$-modules with a Hilbert dual. Then the map $I:M'\to N'$ is an isometric inclusion. If there exists $n\in N$ such that $\|n\|_N>\|\widehat n|_M\|_{M'}$ then $N'=I(M')\oplus K$ for some non-zero $K$.

\end{thm}
\begin{proof}

Let us calculate the composition $PI:M'\to M'$.
For $m,m'\in M$, we have
\begin{eqnarray*}
\langle PI(\widehat m),\widehat m'\rangle_{M'}&=&\langle I(\widehat m),I(\widehat m')\rangle_{N'}\\
&=&\langle \widehat{\alpha(m)},\widehat{\alpha(m')}\rangle_{N'}\\
&=&\langle\alpha(m),\alpha(m')\rangle_N\\
&=&\langle m,m'\rangle_M\\
&=&\langle \widehat m,\widehat m'\rangle_{M'},
\end{eqnarray*}
hence, $\langle PI(\widehat m)-\widehat m,\widehat m'\rangle_{M'}=0$ for any $m'\in M$, thus, as $M\subset M'$ is thick, we conclude that $PI(\widehat m)=\widehat m$ for any $m\in M$.

Note that $PI$ is selfadjoint, and $(PI)|_M=\id_M$. This suffices to show that $PI=\id_{M'}$:
$$
\langle PI(f),\widehat m\rangle_{M'}=\langle f,PI(\widehat m)\rangle_{M'}=\langle f,\widehat m\rangle_{M'},\quad f\in M',
$$
hence, by thickness of $M$ in $M'$, we conclude that $PI(f)=f$ for any $f\in M'$.

Then $IP:N'\to N'$ is a projection with range $M'$, and both $P$ and $I$ are contractions. It follows from (\ref{1}) that
$$
\langle \widehat m,P(\widehat n)\rangle_{M'}=\langle\widehat{\alpha(m)},\widehat n\rangle_{N'}=\langle \alpha(m),n\rangle_N=\widehat n|_M(m)
$$
for any $m\in M$, $n\in N$, hence $P(\widehat n)=\widehat n|_M$ for any $n\in N$.

Let $n\in N$ satisfy $\|n\|_N>\|\widehat n|_M\|_{M'}$. Then $\|P(\widehat n)\|_{M'}<\|n\|_N$, hence $\|IP(\widehat n)\|<\|n\|_N$. If $IP=\id_{N'}$ then this cannot be true, hence the projection $IP$ is not the identity map.
Set $K=(\id_{N'}-IP)(N')$.

\end{proof}

\begin{cor}
Let $M\subset N$ be a thick submodule, and let both $M$ and $N$ be Hilbert $C^*$-modules with a Hilbert dual. If there exists $n\in N$ such that $\|n\|_N > \|\widehat n|_M\|_{M'}$ then there
exists $g\in N'$ such that $g|_M=0$.

\end{cor}
\begin{proof}
Let $K$ be as in Theorem \ref{Thm}, and let $g\in K$, $g\neq 0$. Then $\langle g,f\rangle'=0$
for any $f\in M'$, hence $g|_M=0$.

\end{proof}