You have quite a few columns in your table, and each column header is quite wide. To make the table fit in the textblock, I suspect you'll need to
- reduce the font size used in the table slightly,
- reduce the amount of inter-column whitespace, and
- reduce the widths of columns 2 and 3 by splitting their headers over two consecutive lines.
Separately, I'd also recommend you use the commands \toprule, \midrule, and \bottomrule provided by the booktabs package and that you create a command named, say, \norm, to denote the L_2 norm expressions. By creating such a command, you'll have a much easier time in the future if you ever decide to change the appearance of the \norm function.
Finally, you didn't specify which font size, paper width, and margin widths you employ, so I've had to make some assumptions about these important parameters in the MWE below. The MWE starts with a horizontal line that spans the width of the text block to give you an idea of the value of this important parameter.

\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry} % assume 1" margins
\usepackage{amsmath,booktabs}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\begin{document}
\noindent Width of text block:
\hrule
\begin{table}[ht]
\small % reduce font size by about 10%
\caption{My table}
\centering
\setlength\tabcolsep{2.5pt} % default value: 5pt
\begin{tabular}{@{}l *{6}{c} @{}} % remove blank spaces at ends of table
\toprule
Methods &
computing &
iterative &
$\norm{A X_k A - A}_2$ &
$\norm{X_k A X_k - X_k}_2$ &
$\norm{(A X_k)^* - A X_k}_2$ &
$\norm{(A X_k)^* - A X_k}_2$ \\
& time & times\\
\midrule
method() & & & & & & \\
proposed method & & & & & & \\
\bottomrule
\end{tabular}
\end{table}
\end{document}
\setlength{\tabcolsep}{2pt}. If it doesn't work, and it probably won't, you can also reduce the font by using\small. And if it still isn't enough, you should consider rewriting your column headers in a shorter way. – T. Verron Sep 24 '12 at 13:57