def _onenormest_core(A, AT, t, itmax):
<EOL>A_linear_operator = aslinearoperator(A)<EOL>AT_linear_operator = aslinearoperator(AT)<EOL>if itmax < <NUM_LIT:2>:<EOL><INDENT>raise ValueError('<STR_LIT>')<EOL><DEDENT>if t < <NUM_LIT:1>:<EOL><INDENT>raise ValueError('<STR_LIT>')<EOL><DEDENT>n = A.shape[<NUM_LIT:0>]<EOL>if t >= n:<EOL><INDENT>raise ValueError('<STR_LIT>')<EOL><DEDENT>nmults = <NUM_LIT:0><EOL>nresamples = <NUM_LIT:0><EOL>X = np.ones((n, t), dtype=float)<EOL>if t > <NUM_LIT:1>:<EOL><INDENT>for i in range(<NUM_LIT:1>, t):<EOL><INDENT>resample_column(i, X)<EOL><DEDENT>for i in range(t):<EOL><INDENT>while column_needs_resampling(i, X):<EOL><INDENT>resample_column(i, X)<EOL>nresamples += <NUM_LIT:1><EOL><DEDENT><DEDENT><DEDENT>X /= float(n)<EOL>ind_hist = set()<EOL>est_old = <NUM_LIT:0><EOL>S = np.zeros((n, t), dtype=float)<EOL>k = <NUM_LIT:1><EOL>ind = None<EOL>while True:<EOL><INDENT>Y = np.asarray(A_linear_operator.matmat(X))<EOL>nmults += <NUM_LIT:1><EOL>mags = [norm_1d_1(Y[:, j]) for j in range(t)]<EOL>est = np.max(mags)<EOL>best_j = np.argmax(mags)<EOL>if est > est_old or k == <NUM_LIT:2>:<EOL><INDENT>if k >= <NUM_LIT:2>:<EOL><INDENT>ind_best = ind[best_j]<EOL><DEDENT>w = Y[:, best_j]<EOL><DEDENT>if k >= <NUM_LIT:2> and est <= est_old:<EOL><INDENT>est = est_old<EOL>break<EOL><DEDENT>est_old = est<EOL>S_old = S<EOL>if k > itmax:<EOL><INDENT>break<EOL><DEDENT>S = sign_round_up(Y)<EOL>if every_col_of_X_is_parallel_to_a_col_of_Y(S, S_old):<EOL><INDENT>break<EOL><DEDENT>if t > <NUM_LIT:1>:<EOL><INDENT>for i in range(t):<EOL><INDENT>while column_needs_resampling(i, S, S_old):<EOL><INDENT>resample_column(i, S)<EOL>nresamples += <NUM_LIT:1><EOL><DEDENT><DEDENT><DEDENT>Z = np.asarray(AT_linear_operator.matmat(S))<EOL>nmults += <NUM_LIT:1><EOL>h = [norm_1d_inf(row) for row in Z]<EOL>if k >= <NUM_LIT:2> and max(h) == h[ind_best]:<EOL><INDENT>break<EOL><DEDENT>h_i_pairs = zip(h, range(n))<EOL>h, ind = zip(*sorted(h_i_pairs, reverse=True))<EOL>if t > <NUM_LIT:1>:<EOL><INDENT>if set(ind[:t]) <= ind_hist:<EOL><INDENT>break<EOL><DEDENT>unused_entries = [i for i in ind if i not in ind_hist]<EOL>used_entries = [i for i in ind if i in ind_hist]<EOL>ind = unused_entries + used_entries<EOL><DEDENT>for j in range(t):<EOL><INDENT>X[:, j] = elementary_vector(n, ind[j])<EOL><DEDENT>ind_hist.update(ind[:t])<EOL>k += <NUM_LIT:1><EOL><DEDENT>v = elementary_vector(n, ind_best)<EOL>return est, v, w, nmults, nresamples<EOL>
Compute a lower bound of the 1-norm of a sparse matrix.

Parameters
----------
A : ndarray or other linear operator
    A linear operator that can produce matrix products.
AT : ndarray or other linear operator
    The transpose of A.
t : int, optional
    A positive parameter controlling the tradeoff between
    accuracy versus time and memory usage.
itmax : int, optional
    Use at most this many iterations.

Returns
-------
est : float
    An underestimate of the 1-norm of the sparse matrix.
v : ndarray, optional
    The vector such that ||Av||_1 == est*||v||_1.
    It can be thought of as an input to the linear operator
    that gives an output with particularly large norm.
w : ndarray, optional
    The vector Av which has relatively large 1-norm.
    It can be thought of as an output of the linear operator
    that is relatively large in norm compared to the input.
nmults : int, optional
    The number of matrix products that were computed.
nresamples : int, optional
    The number of times a parallel column was observed,
    necessitating a re-randomization of the column.

Notes
-----
This is algorithm 2.4.