Subspace-constrained partial update method for high-dimensional adaptive processing systems

Abstract

A method is explained for any adaptive processor processing digital signals by adjusting signal weights on digital signal(s) it handles, to optimize adaptation criteria responsive to a functional purpose or externalities (transient, temporary, situational, and even permanent) of that processor. Adaptation criteria for the adaptive algorithm may be any combination of a signal or parameter estimation, and measured quality(ies).

This method performs a linear transformation adapting parameters from M to (M.sub.1+L) dimensions in each adaptation event, such that M.sub.1 weights are updated without constraints and M.sub.0=M−M.sub.1 weights are forced by soft constraints into an L-dimensional subspace they spanned at the beginning of the adaptation period. The same dimensionality reduction, using the same linear transformation, is applied to the input data. The reduced-dimensionality weights are then adapted using the identical optimization strategy employed by the processor, except with input data that has also been reduced in dimensionality.

Claims

1. A method for digital signal processing (wherein ‘digital’ refers to the nature of the computational processing and ‘signal’ refers to analog electromagnetic waveforms) on devices employing at least one adaptive processor that employs large numbers of adaptation weights for any adaptation criterion of the set of signal estimation, parameter estimation, measured quality, and any combination thereof for “adapt-path” operations used to tune the adaptive processor, not “data-path” operations used by the adaptive processor during and after tuning, said method comprising: for each adaptation event having M-dimensions, performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event, said linear transformation further comprising: adapting M.sub.1 weights without constraints; and, adapting M.sub.0=M−M.sub.1 weights subjected to L soft constraints forcing them into an L-dimensional subspace spanned by the those weights; applying the same dimensionality reduction to input data using the same linear transformation; and, adapting the reduced-dimensionality weights using the same optimization strategy employed by the adaptive processor, except with the input data to which the same dimensionality reduction has been applied.

2. A method as in claim 1, wherein the step of performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event further comprises: applying a subspace constraint described in the form
M.sub.0.sup.T(n)w′∝M.sub.0.sup.T(n)w
=M.sub.0.sup.T(n)wg.sub.0; jointly adjusting the scalar hand-set multiplier g.sub.0 and the update-set weights w.sub.1=M.sub.1(n)w to optimize an unconstrained criterion metric F(w;n) over adapt block n, said metric determined by $w \leftarrow \arg .Math. \underset{w^{'}}{opt} .Math. F (w^{'}; n)$ subject to additional linear constraint (w′).sub.m∈M.sub.0.sub.(n)=(w).sub.m∈M.sub.0.sub.(n); and, using the resulting full output weight vector in the adaptation event.

3. A method as in claim 2 wherein the full output weight vector is efficiently computed using vector-scalar multiplies and multiply-free multiplexing (MUX) operations.

4. A method as in claim 2, wherein the step of jointly adjusting the scalar hand-set multiplier g.sub.0 and the update-set weights w.sub.1=M.sub.1(n)w to optimize an unconstrained criterion metric F(w;n) over adapt block n further comprises using a (M.sub.1+1)×1 enhanced weight vector {tilde over (w)}= $(\begin{matrix} w_{1} \\ g_{0} \end{matrix})$ using optimization formula $\tilde{w} \leftarrow \arg .Math. \underset{{\tilde{w}}^{'}}{opt} .Math. F ({\tilde{w}}^{'}; n)$ over each data block to produce the full output weight vector w=M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0g.sub.0.

5. A method as in claim 4 wherein the full output weight vector is efficiently computed using vector-scalar multiplies and multiply-free multiplexing (MUX) operations.

6. A method for implementing partial-update methods (PUMs) in any adaptive processor that adjusts weights to optimize an adaptation criterion using any of a signal estimation and a parameter estimation algorithm in digital signal processing (wherein ‘digital’ refers to the nature of the computational processing and ‘signal’ refers analog electromagnetic waveforms) when said adaptive processor employs large numbers of adaptation weights for any adaptation criterion of the set of signal estimation, parameter estimation, measured quality, and any combination thereof for “adapt-path” operations used to tune the adaptive processor, not “data-path” operations used by the adaptive processor during and after tuning, said method comprising: for each adaptation event comprising a partial-update effected by the adaptive processor for an adapt path operation having M-dimensions, performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in said partial update, said linear transformation further comprising: adapting M.sub.1 weights without constraints; and, adapting M.sub.0=M−M.sub.1 weights subjected to L soft constraints forcing them into an L-dimensional subspace spanned by the those weights; applying the same dimensionality reduction to input data using the same linear transformation; and, adapting the reduced-dimensionality weights using the same optimization strategy employed by the adaptive processor, except with the input data to which the same dimensionality reduction has been applied.

7. A method as in claim 6, wherein the step of performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event further comprises: replacing a hard linear constraint describable in the form M.sub.0(n)w′=M.sub.0(n)w with a softer subspace constraint described in the form
M.sub.0.sup.T(n)w′∝M.sub.0.sup.T(n)w
=M.sub.0.sup.T(n)wg.sub.0; jointly adjusting the scalar hand-set multiplier g.sub.0 and the update-set weights w.sub.1=M.sub.1(n)w to optimize an unconstrained criterion metric F(w;n) over adapt block n, said metric determined by $w \leftarrow \arg .Math. \underset{w^{'}}{opt} .Math. F (w^{'}; n)$ subject to additional linear constraint (w′).sub.m∈M.sub.0.sub.(n)=(w).sub.m∈M.sub.0.sub.(n); and, using the resulting full output weight vector in the adaptation event

8. A method as in claim 6 for partial-update affine projections, further comprising: separating w into update-set and held-set components w.sub.1 and w.sub.0 using multiply-free demultiplexing (DMX) operations; for SCPU-AP/NLMS SCPU-BLS algorithms with μ<1, construct a (M.sub.1+1)×1 dimensional weight matrix $\tilde{w} = (\begin{matrix} w_{1} \\ 1 \end{matrix});$ separating X(n) into update-set and held-set components X.sub.1(n) and X.sub.0(n) using multiply-free columnar DMX operations; computing y.sub.0(n)=X.sub.0(n)w.sub.0; specifically for any SCPU-AP/NLMS algorithm, further computing y.sub.1(n)=X.sub.1(n)w.sub.1 and y(n)=y.sub.1(n)+y.sub.0(n); constructing a N×(M.sub.1+1) dimensional SCPU data matrix
{tilde over (X)}(n)=[X.sub.1(n)y.sub.0(n)]; optimizing {tilde over (w)} using the original unconstrained algorithm, with dimensionality reduced from M to M.sub.1+1; updating w.sub.1 and w.sub.0 using w.sub.1←[({tilde over (w)}).sub.m].sub.m=1.sup.M.sup.1, w.sub.0←({tilde over (w)}).sub.M.sub.1.sub.+1w.sub.0; and, reconstructing the linear combiner weights using w=M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0.

9. A method as in claim 6 wherein the adaptation arises from and must apply over a multiport digital signal processing hardware any of an affine-projection and block least-squares adaptation algorithm.

10. A method as in claim 9 wherein the multiport digital signal processing is uncoupled.

11. A method as in claim 9 wherein the multiport digital signal processing is fully-coupled.

12. A method for digital signal processing (wherein ‘digital’ refers to the nature of the computational processing and ‘signal’ refers to analog electromagnetic waveforms) on devices employing at least one adaptive processor that employs large numbers of adaptation weights for any adaptation criterion of the set of signal estimation, parameter estimation, measured quality, and any combination thereof for “adapt-path” operations used to tune the adaptive processor, not “data-path” operations used by the adaptive processor during and after tuning, said method comprising: for each adaptation event having M-dimensions, performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event, said linear transformation further comprising: adapting M.sub.1 weights without constraints; and, adapting M.sub.0=M−M.sub.1 weights subjected to L soft constraints forcing them into an L-dimensional subspace spanned by the those weights; applying the same dimensionality reduction to input data using the same linear transformation; and, adapting the reduced-dimensionality weights using substantively the same optimization strategy employed by the adaptive processor for the input data to which the same dimensionality reduction has been applied.

13. A method as in claim 1 for partially blind methods in which the reference vector s(n) is partially known at the receive processor over adapt block n, as the reference vector has any of an unknown carrier and timing offset relative to the sequence contained in the input data sequence.

14. A method as in claim 13 for any of timing and carrier tracking methods, wherein s(n) has an unknown offset between the input data and an original transmitted signal containing the reference signal, further comprising: replacing the nonblind weight adaptation algorithm
{tilde over (w)}←(1−μ){tilde over (w)}+μ{tilde over (X)}.sup.†(n)s(n), 0<μ≦1
with
{tilde over (w)}←(1−μ){tilde over (w)}+μ{tilde over (X)}.sup.†(n)(s({circumflex over (n)}.sub.off;n)∘δ(ω.sub.off))
s(n.sub.off;n)=[s(nN+n.sub.sym+n.sub.off)].sub.n.sub.sym.sub.=1.sup.N
δ(ω.sub.off)=[e.sup.jω.sup.off.sup.n.sup.sym].sub.n.sub.sym.sub.=1.sup.N where {s(n.sub.sym)} is a component of the transmitted signal that is known over the adapt block except for the unknown offset; and, optimizing the unknown offset over each adapt block by setting ${{\hat{ω}}_{off} (n), {\hat{n}}_{off} (n)} = \arg .Math. \max_{ω_{off}, n_{off}} .Math. η (ω_{off}, n_{off}; n), .Math. \begin{matrix} η (ω_{off}, n_{off}; n) = .Math. \frac{{.Math. {\tilde{Q}}^{H} (n) .Math. (s (n_{off}; n) .Math. •δ (ω_{off})) .Math.}_{2}^{2}}{{.Math. s (n_{off}; n) .Math.}_{2}^{2}}, \\ = .Math. \frac{{.Math. {.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {\tilde{q}}^{*} (n_{sym}) .Math. s (nN + n_{sym} + n_{off}) .Math. e^{{jω}_{off} .Math. n_{sym}} .Math.}_{2}^{2}}{{.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {.Math. s (nN + n_{sym} + n_{off}) .Math.}^{2}}, \end{matrix}$ where {tilde over (Q)}=[{tilde over (q)}(1) . . . {tilde over (q)}(N)].sup.T is the Q-component of the QRD of {tilde over (X)}(n) using fast Fourier transform (FFT) methods if the frequency offset ω is completely unknown (acquisition phases), and using Gauss-Newton or Newton methods if the frequency offset ω is known closely (tracking phases).

15. A method as in claim 1 for fully blind methods in which the reference vector is unknown but has some known, exploitable structure.

16. A method as in claim 1 for property-mapping methods in which s(n) is a member of a known property set, said method further comprising: replacing the non-blind weight adaptation algorithm $\tilde{w} \leftarrow (1 - μ) .Math. \tilde{w} + μ .Math. .Math. {\tilde{X}}^{†} (n) .Math. s (n), .Math. 0 < μ \leq 1$ $with$ $y (n) = \tilde{X} (n) .Math. \tilde{w}, .Math. \hat{s} (n) = \arg .Math. \min_{s \in  (n)} .Math. .Math. s - y (n) .Math., .Math. and$ $\tilde{w} \leftarrow (1 - μ) .Math. \tilde{w} + μ .Math. .Math. {\tilde{X}}^{†} (n) .Math. \hat{s} (n);$ where custom-character (n) is a desired signal set, potentially variable as a function of adapt block n, that s(n) is known to belong to.

17. A method as in claim 1 for dominant-mode prediction (DMP) methods, in which s(n) is known to be substantively present in a linear subspace with any of a known or estimable structure, said method further comprising: using an enhanced weight algorithm effecting $\tilde{w} = \arg .Math. \max_{w \in ℂ^{M_{1} + 1}} .Math. \tilde{γ} (ω; n), .Math. \tilde{γ} (w; n) = \frac{w^{H} ({\tilde{X}}_{s}^{H} (n) .Math. {\tilde{X}}_{s} (n)) .Math. w}{w^{H} ({\tilde{X}}_{⊥}^{H} (n) .Math. {\tilde{X}}_{⊥} (n)) .Math. w}, {\begin{matrix} {\tilde{X}}_{s} (n) = U_{s}^{H} (n) .Math. \tilde{X} (n) \\ {\tilde{X}}_{⊥} (n) = U_{⊥}^{H} (n) .Math. \tilde{X} (n) \end{matrix}$ wherein the enhanced combiner weights {tilde over (w)}.sub.max and the maximal value of {tilde over (γ)}.sub.max, are equal to the dominant solution {{tilde over (γ)}.sub.1,{tilde over (w)}.sub.1} of the DMP eigenequation
{tilde over (γ)}.sub.m({tilde over (X)}.sub.⊥.sup.H(n){tilde over (X)}.sub.⊥(n)){tilde over (w)}.sub.m=({tilde over (X)}.sub.s.sup.H(n){tilde over (X)}.sub.s(n)){tilde over (w)}.sub.m, {tilde over (γ)}.sub.m≧{tilde over (γ)}.sub.m+1 and the dominant eigenvalue {tilde over (γ)}.sub.1 also provides an estimate of the SINR of the combiner output signal, such that the dominant eigenvalue {tilde over (γ)}.sub.1 also is usable both to detect the target signal, and to search over postulated subspaces to find the subspace that most closely contains or rejects s(n).

18. A method as in claim 1 for conjugate self-coherence restoral (C-SCORE) methods in which s(n) is known to have substantive conjugate self-coherence at some known or estimable frequency offset ω, such that $\frac{.Math. {.Math.}_{n_{sym} = 1}^{N} .Math. .Math. s^{2} (nN + n_{sym}) .Math. e^{- jω .Math. .Math. n_{sym}} .Math.}{{.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {.Math. s (nN - n_{sym}) .Math.}^{2}} \approx 1$ said method further comprising: using for the enhanced weight algorithm for a postulated twice-carrier offset ω, $\begin{matrix} \tilde{w} = \arg .Math. \max_{w \in ℂ^{M_{1} + 1}} .Math. \tilde{ρ} (w | ω; n), \\ \tilde{ρ} (w | ω; n) = \frac{.Math. w^{H} ({\tilde{X}}^{H} (n) .Math. Δ (ω) .Math. {\tilde{X}}^{*} (n)) .Math. w^{*} .Math.}{w^{H} ({\tilde{X}}^{H} (n) .Math. \tilde{X} .Math. (n)) .Math. w}, .Math. Δ (ω) = diag .Math. {e^{jω .Math. .Math. n_{sym}}}_{n_{sym} = 1}^{N} \end{matrix}$ wherein the enhanced combiner weights {tilde over (w)}.sub.max and the maximal value {tilde over (w)}.sub.max are equal to the dominant solution {{tilde over (ρ)}.sub.1(ω),{tilde over (w)}.sub.1(ω)} of the C-SCORE pseudo-eigenequation,
{tilde over (ρ)}.sub.m(ω)({tilde over (X)}.sup.H(n){tilde over (X)}((n)){tilde over (w)}.sub.m(ω)=({tilde over (X)}.sup.H(n)Δ(ω){tilde over (X)}*(n)){tilde over (w)}.sub.m*(ω), {tilde over (ρ)}.sub.m≧{tilde over (ρ)}.sub.m+1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0020] The present invention is illustrated in the attached drawings as described herein.

[0021] FIG. 1 is a view of an optimization approach used in a system employing a prior-art nonblind single-port unconstrained adaptation algorithm.

[0022] FIG. 2 is a view of an optimization approach used in a system employing a prior-art nonblind single-port partial-update (PU) adaptation algorithm.

[0023] FIG. 3 is a view of an optimization approach used in a system employing a nonblind single-port subspace-constrained partial update (SCPU) adaptation algorithm.

[0024] FIG. 4 is a view of a nonblind single-port SCPU adapt-path weight update procedure, depicting use of projection matrices (implemented using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of an unconstrained single-port weight adaptation algorithm of arbitrary type and structure after the subspace separation procedure.

[0025] FIG. 5 is a view of a nonblind uncoupled multipart SCPU adapt-path weight update procedure, depicting use of projection matrices (implemented using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of parallel banks of reduced-complexity unconstrained single-port weight adaptation algorithms of arbitrary type and structure after the subspace separation procedure.

[0026] FIG. 6 is a view of a nonblind fully-coupled multipart SCPU adapt-path weight update procedure, depicting use of projection matrices (implemented using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of an unconstrained multipart weight adaptation algorithm of arbitrary type and structure after the subspace separation procedure.

DETAILED DESCRIPTION OF THE DRAWINGS

[0027] FIG. 1 is a view of an optimization approach used in a system employing a prior-art nonblind single-port unconstrained adaptation algorithm. On a first path, a vector processor [1] provides a sequence of data vectors x(n.sub.sym)=[x.sub.1(n.sub.sym) . . . x.sub.M(n.sub.sym)].sup.T, each data vector having dimension M×1, where n.sub.sym is a symbol index, and where M is a real positive integer, referred to here as the degrees-of-freedom (DoF's) of the system, and (•).sup.T denotes the matrix transpose operation. As part of a data-path processing procedure, the data vector sequence x(n.sub.sym) is then passed through a linear combiner [3] that performs a matrix multiplication of x(n.sub.sym) by a weight vector w=[w.sub.1 . . . w.sub.M].sup.T having dimension M×1, resulting in an output data scalar y(n.sub.sym)=x.sup.T(n.sub.sym)w having dimension N×1.

[0028] As part of an adapt-path processing procedure that is a focus of the invention, the data vector sequence x(n.sub.sym) is also passed into a bank of M 1:N serial-to-parallel (S/P) convertors [2] that converts the vector data sequence into a sequence of data matrices X(n)=[x(nN+1) . . . x(nN+N)].sup.T, each data matrix having dimension N×M, where N is a real-positive integer, referred to here as the block length of the adaptation algorithm, and n is an adapt block index.

[0029] On a second path, and also as part of an adapt-path processing procedure, a sequence of reference scalars s(n.sub.sym) is provided by a reference generator [4], each reference scalar having dimension 1×1. In the nonblind adaptation algorithm shown in FIG. 1, the reference scalars s(n.sub.sym) are known at the receiver, and are correlated with some component of the data vector x(n.sub.sym) in some known manner; however, in other system implementations, the reference scalars may be members of a set of possible known received signal components, or may be derived from the output data vector in some manner.

[0030] The reference scalars are then passed into a single 1:N serial-to-parallel (S/P) convertor [5] that converts the scalar symbol sequence into a sequence of reference vectors s(n), each vector reference data symbol having dimension N×1. The reference vector s(n) is then compared with the data matrix X(n) (from the bank of M 1:N serial-to-parallel converters [2]) over each adapt block, and used to generate a weight vector w using an unconstrained adaptation algorithm [6] that adjusts every element of w to optimize a metric of similarity between the output data vector y(n)=X(n)w and the reference vector s(n), e.g., the sum-of-squares error metric F(w;n)=∥s(n)−X(n)w∥.sub.2.sup.2, where ∥•∥.sub.2 denotes the L2 vector norm. The weights are then passed to the data-path processor [3], where they are used to process the input data vectors on a symbol-by-symbol basis.

[0031] It should be noted that the data matrices and reference vectors do not need to be contiguous, internally or between adapt blocks on the adapt-paths. However, the input data matrices and reference vectors should have internally consistent symbol indices.

[0032] FIG. 2 is a view of an optimization approach used in a system employing a prior-art nonblind single-port partial-update (PU) adaptation algorithm. On a first path, a vector processor [1] provides a sequence of data vectors x(n.sub.sym)=[x.sub.1(n.sub.sym) . . . x.sub.M(n.sub.sym)].sup.T, each data vector having dimension M×1, where n.sub.sym is a symbol index, and where M is a real positive integer, referred to here as the degrees-of-freedom (DoF's) of the system, and (•).sup.T denotes the matrix transpose operation. As part of a data-path processing procedure, the data vector sequence x(n.sub.sym) is then passed through a linear combiner [3] that performs a matrix multiplication of x(n.sub.sym) by a weight vector w=[w.sub.1 . . . w.sub.M].sup.T having dimension M×1, resulting in an output data scalar y(n.sub.sym)=x.sup.T(n.sub.sym)w having dimension N×1.

[0033] As part of an adapt-path processing procedure that is a focus of the invention, the data vector sequence x(n.sub.sym) is also passed into a bank of M 1:N serial-to-parallel (S/P) convertors [2] that converts the vector data sequence into a sequence of data matrices X(n)=[x(nN+1) . . . x(nN+N)].sup.T, each data matrix having dimension N×M, where N is a real-positive integer, referred to here as the block length of the adaptation algorithm, and n is an adapt block index.

[0034] On a second path, and also as part of an adapt-path processing procedure, a sequence of reference scalars s(n.sub.sym) is provided by a reference generator [4], each reference scalar having dimension 1×1. In the nonblind adaptation algorithm shown in FIG. 2, the reference scalars s(n.sub.sym) are known at the receiver, and are correlated with some component of the data vector x(n.sub.sym) in some known manner; however, in other system implementations, the reference scalars may be members of a set of possible known received signal components, or may be derived from the output data vector in some manner.

[0035] The reference scalars are then passed into a single 1:N serial-to-parallel (S/P) convertor [5] that converts the scalar symbol sequence into a sequence of reference vectors s(n), each vector reference data symbol having dimension N×1.

[0036] On a third path, and also as part of an adapt-path processing procedure, an update-set selection algorithm [7] is used to generate a sequence of M.sub.1-element update-sets custom-character .sub.1(n)={m∈{1, . . . , M}: m(1;n), . . . , m(M.sub.1;n)} and complementary M.sub.0-element held-sets .sub.0(n)={m∈{1, . . . , M}: m.Math..sub.1(n)} over each adapt block, such that M.sub.0=M−M.sub.1, .sub.0(n)∪.sub.1(n)={1, . . . , M}, and .sub.0(n)∪.sub.1(n)={ } within adapt block n. The set selection strategy can be adjusted using deterministic, random, pseudo-random, or data-derived methods. In the partial-update optimization approach shown in FIG. 2, the update-set held-set { custom-character .sub.1(n),.sub.0(n)} are further used to generate update-set and held-set projection matrices [9] {M.sub.1(n),M.sub.0(n)}, where M.sub.l(n)=[e.sub.M(m.sub.l)].sub.m.sub.l.sub.∈.sub.l.sub.(n) for l=0,1, and where e.sub.M(m.sub.l)=[δ(m−m.sub.l)].sub.m=1.sup.M is the m.sub.l.sup.th M×1 Euclidean basis vector and δ(k) is the Kronecker delta function.

[0037] The reference vector s(n) is then compared with the data matrix X(n) over each adapt block, and used to generate a weight vector w using a hard-constrained adaptation algorithm [8] that adjusts only the elements of w in the update-set, i.e., (w).sub.m∈ custom-character .sub.1.sub.(n), to optimize a metric of similarity between the output data vector y(n)=X(n)w and the reference vector s(n), e.g., the sum-of-squares error metric F(w;n)=∥s(n)−X(n)w∥.sub.2.sup.2, while holding the elements of w in the held-set, i.e., (w).sub.m∈.sub.0.sub.(n), equal to the same values held by those weight elements over the previous adapt block. This can be expressed as optimization of existing weight vector w to form new weight vector w′, subject to hard linear constraint M.sub.0.sup.T(n)w′=M.sub.0.sup.T(n)w. The weights are then passed to the data-path processor [3], where they are used to process the input data vectors on a symbol-by-symbol basis.

[0038] It should be noted that the data matrices and reference vectors do not need to be contiguous, internally or between adapt blocks on the adapt-paths. However, the input data matrices and reference vectors should have internally consistent symbol indices.

[0039] FIG. 3 is a view of an optimization approach used in a system employing a new nonblind single-port subspace-constrained partial-update (SCPU) adaptation algorithm. On a first path, a vector processor [1] provides a sequence of data vectors x(n.sub.sym)=[x.sub.1(n.sub.sym) . . . x.sub.M(n.sub.sym)].sup.T, each data vector having dimension M×1, where n.sub.sym is a symbol index, and where M is a real positive integer, referred to here as the degrees-of-freedom (DoF's) of the system, and (•).sup.T denotes the matrix transpose operation. As part of a data-path processing procedure, the data vector sequence x(n.sub.sym) is then passed through a linear combiner [3] that performs a matrix multiplication of x(n.sub.sym) by a weight vector w=[w.sub.1 . . . w.sub.M].sup.T having dimension M×1, resulting in an output data scalar y(n.sub.sym)=x.sup.T(n.sub.sym)w having dimension N×1.

[0040] As part of an adapt-path processing procedure that is a focus of the invention, the data vector sequence x(n.sub.sym) is also passed into a bank of M 1:N serial-to-parallel (S/P) convertors [2] that converts the vector data sequence into a sequence of data matrices X(n)=[x(nN+1) . . . x(nN+N)].sup.T, each data matrix having dimension N×M, where N is a real-positive integer, referred to here as the block length of the adaptation algorithm, and n is an adapt block index.

[0041] On a second path, a sequence of reference scalars s(n.sub.sym) is provided by a reference generator [4], each reference scalar having dimension 1×1. In the nonblind adaptation algorithm shown in FIG. 3, the reference scalars s(n.sub.sym) are known at the receiver, and are correlated with some component of the data vector x(n.sub.sym) in some known manner; however, in other system implementations, the reference scalars may be members of a set of possible known received signal components, or may be derived from the output data vector in some manner.

[0042] The reference scalars are then passed into a single 1:N serial-to-parallel (S/P) convertor [5] that converts the scalar symbol sequence into a sequence of reference vectors s(n), each vector reference data symbol having dimension N×1.

[0043] On a third path, an update-set selection algorithm [7] is used to generate a sequence of M.sub.1-element update-sets custom-character .sub.1(n)={m∈{1, . . . , M}: m(1;n), . . . , m(M.sub.1;n)} and complementary M.sub.0-element held-sets .sub.0(n)={m∈{1, . . . , M}: m.Math.M.sub.1(n)} over each adapt block, such that M.sub.0=M−M.sub.1, .sub.0(n)∪.sub.1(n)={1, . . . , M}, and .sub.0(n)∪.sub.1(n)={ } within adapt block n. The set selection strategy can be adjusted using deterministic, random, pseudo-random, or data-derived methods. In the partial-update optimization approach shown in FIG. 3, the update-set held-set { custom-character .sub.1(n),.sub.0(n)} are further used to generate update-set and held-set projection matrices [9] {M.sub.1(n),M.sub.0(n)}, where M.sub.l(n)=[e.sub.M(m.sub.l)].sub.m.sub.l.sub.M.sub.l.sub.(n) for l=0,1, and where e.sub.M(m.sub.l)=[δ(m−m.sub.l)].sub.m=1.sup.M is the m.sub.l.sup.th M×1 Euclidean basis vector and δ(k) is the Kronecker delta function.

[0044] The reference vector s(n) is then compared with the data matrix X(n) over each adapt block, and used to generate a weight vector w using a subspace-constrained adaptation algorithm [10] that adjusts the elements of w in the update-set, i.e., (w).sub.m∈ custom-character .sub.1.sub.(n), to optimize a metric of similarity between the output data vector y(n)=X(n)w and the reference vector s(n), e.g., the sum-of-squares error metric F(w;n)=∥s(n)−X(n)w∥.sub.2.sup.2, while optimizing the elements of w in the held-set, i.e., (w).sub.m∈.sub.0.sub.(n), to a scalar multiple of the values held by those weight elements over the previous adapt block. This can be expressed as optimization of existing weight vector w to form new weight vector w′, subject to subspace constraint M.sub.0.sup.T(n)w′=g.sub.0M.sub.0.sup.T(n)w, where g.sub.0 is an unknown scalar that is also optimized by the algorithm. The weights are then passed to the data-path processor [3], where they are used to process the input data vectors on a symbol-by-symbol basis.

[0045] It should be noted that the data matrices and reference vectors do not need to be contiguous, internally or between adapt blocks on the adapt-paths. However, the input data matrices and reference vectors should have internally consistent symbol indices.

[0046] FIG. 4 is a view of a nonblind, single-port, SCPU adapt-path weight update method, depicting use of projection matrices (implemented using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of an unconstrained single-port weight adaptation algorithm of arbitrary type and structure after the subspace separation procedure. Over adapt block n, the N×M data matrix X(n) provided by the 1:N S/P bank [2] (not shown) is separated into an N×M.sub.1 dimensional update-set data matrix X.sub.1(n)=X(n)M.sub.1(n) and an N×M.sub.0 dimensional held-set data matrix X.sub.0(n)=X(n)M.sub.0(n), using a columnar matrix demultiplexer (DMX) [11] and the update-set and held-set projection matrices provided over adapt block n [7].

[0047] An M×M.sub.0 dimensional held-set projection matrix M.sub.0(n) is additionally used to extract the M.sub.0×1 dimensional held-set combiner weights w.sub.0=M.sub.0.sup.T(n)w from the M×1 dimensional combiner weights w stored in current memory [12], e.g., computed in prior adapt blocks, using a held-set weight extractor [13]. These held-set combiner weights w.sub.0 are used to multiply the held-set data matrix X.sub.0(n) from the columnar matrix demultiplexer (DMX) [11] through a linear combiner [14], yielding a N×1 held-set output data vector y.sub.0(n)=X.sub.0(n)w.sub.0 . X.sub.1(n) and y.sub.0(n) are then combined into an N×(M.sub.1+1) enhanced data matrix {tilde over (X)}(n)=[X.sub.1(n) y.sub.0(n)] using a column-wise multiplexing (MUX) operation [15].

[0048] The enhanced data matrix {tilde over (X)}(n) is then input to an unconstrained weight adaptation algorithm [16] that adjusts every element of an (M.sub.1+1)×1 enhanced combiner vector

[00001] $\tilde{w} = (\begin{matrix} w_{1} \\ g_{0} \end{matrix})$

to optimize a metric of similarity between an N×1 reference vector s(n) provided by a reference generator [4] (not shown) and an N×1 output data vector y(n)={tilde over (X)}(n){tilde over (w)} that would be provided by an (M.sub.1+1)-element linear combining operation (not shown). The unconstrained weight adaptation algorithm [16] optimizes the same metric as the unconstrained weight adaptation algorithm [6] depicted in prior art FIG. 1, e.g., the sum-of-squares error metric F(w;n)=∥s(n)−{tilde over (X)}(n){tilde over (w)}∥.sub.2.sup.2. However, the complexity of the unconstrained weight adaptation algorithm is O((M.sub.1+1).sup.v) in [16], rather than O(M.sup.v) in [6], where v is the complexity order of the algorithm, e.g., v=2 if a sum-of-squares metric is used in both Figures.

[0049] The updated (M.sub.1+1)×1 enhanced combiner vector {tilde over (w)} is then demultiplexed (DMX'd) [17] into an updated M.sub.1×1 update-set weight vector w.sub.1 comprising the first M.sub.1 elements of {tilde over (w)}, and a new held-set scalar multiplier g.sub.0 comprising the last element of {tilde over (w)}. The held-set scalar multiplier g.sub.0 is then multiplied by the current M.sub.0×1 held-set weights w.sub.0 [18] to form updated held-set weights w.sub.0←w.sub.0g.sub.0, and multiplexed (MUX'd) [19] with the updated M.sub.1×1 update-set weight vector w.sub.1, in accordance with the current update-set selection algorithm [7], to form updated M×1 dimensional weight vector w=M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0. This weight vector is then stored in memory [12], allowing its use as an initial combiner weight vector in a subsequent adapt block. The weight vector can also be used in the data-path linear combiner (not shown) for parallel or subsequent data-path processing operations used in the overall system.

[0050] FIG. 5 is a view of a nonblind, multiport, uncoupled SCPU adapt-path weight update method, depicting use of projection matrices (implementing using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of parallel banks of reduced-complexity and unconstrained, single-port, weight adaptation algorithms of arbitrary type and structure after the subspace separation step. Over adapt block n, the N×M data matrix X(n) provided by the 1:N S/P bank [2] (not shown) is separated into an N×M.sub.1 dimensional update-set data matrix X.sub.1(n)=X(n)M.sub.1(n) and an N×M.sub.0 dimensional held-set data matrix X.sub.0(n)=X(n)M.sub.0(n), using a columnar matrix demultiplexer (DMX) [10] and the update-set and held-set projection matrices provided over adapt block n from the update-set selection algorithm [7]. On each output port p, where p=1, . . . , P where P is the number of weight ports adapted by the overall algorithm, the M×M.sub.0 dimensional held-set projection matrix M.sub.0(n) is additionally used to extract the M.sub.0×1 dimensional port p held-set combiner weights w.sub.0(p)=M.sub.0.sup.T(n)w(p) from the M×1 dimensional port p combiner weight vector w(p) stored in current memory [20], e.g., computed over a prior adapt block, using a held-set weight extractor [13]. The held-set data matrix X.sub.0(n) is then multiplied by the port p held-set combiner weights w.sub.0 (p) from the held-set weight extractor [13] through a linear combiner [14], yielding N×1 w.sub.0(p) held-set output data vector y.sub.0(n;p)=X.sub.0(n)w.sub.0(p) for each port p. X.sub.1(n) and y.sub.0(n;p) are then combined into an N×(M.sub.1+1) enhanced port p data matrix {tilde over (X)}(n;p)=[X.sub.1(n) y.sub.0(n;p)] using a column-wise multiplexing (MUX) operation [15]. The port p enhanced data matrix is then input to an unconstrained weight adaptation algorithm [21] that adjusts every element of an (M.sub.1+1)×1 port p enhanced combiner vector {tilde over (w)}(p)=

[00002] $(\begin{matrix} w_{1} (p) \\ g_{0} (p) \end{matrix})$

to optimize a metric of similarity between an N×1 port p reference vector s(n;p) provided by a reference generator [4] (not shown) and an N×1 output data vector y(n;p)={tilde over (X)}(n;p){tilde over (w)}(p) that would be provided by an (M.sub.1+1)-element linear combining operation (not shown). The unconstrained weight adaptation algorithm [21] optimizes the same metric as the unconstrained weight adaptation algorithm [6] depicted in prior art FIG. 1, e.g., the sum-of-squares error metric F(w;n,p)=∥s(n;p)−{tilde over (X)}(n;p){tilde over (w)}∥.sub.2.sup.2. However, the complexity of the unconstrained weight adaptation algorithm is O((M.sub.1+1).sup.v) in [21], rather than O(M.sup.v) in [6], where v is the complexity order of the algorithm, e.g., v=2 if a sum-of-squares metric is used in both Figures. Additionally, the weight adaptation algorithm can exploit commonality between the enhanced data matrices {{tilde over (X)}(n;p)}.sub.p=1.sup.P, i.e., the common update-set data matrix X.sub.1(n) contained within each enhanced data matrix, to share results of operations on X.sub.1(n) performed for each algorithm port, resulting in an additional reduction on computational complexity for the overall multiport processor.

[0051] The updated (M.sub.1+1)×1 port p enhanced combiner vector {tilde over (w)}(p) is then demultiplexed (DMX'd) [17] into an updated M.sub.1×1 port p update-set weight vector w.sub.1(p) comprising the first M.sub.1 elements of {tilde over (w)}(p), and a new port p held-set scalar multiplier g.sub.0(p) comprising the last element of {tilde over (w)}(p). The held-set scalar multiplier g.sub.0 (p) is then multiplied by the current (from the held-set weight extractor [13]) M.sub.0×d port p held-set weights w.sub.0 (p) [18] to form updated port p held-set weights w.sub.0(p)←w.sub.0(p)g.sub.0(p), and multiplexed (MUX'd) [19] with the updated M.sub.1×1 port p update-set weight vector w.sub.1(p), in accordance with the current update-set selection algorithm [7], to form updated M×1 dimensional port p weight vector w(p)=M.sub.1(n)w.sub.1(p)+M.sub.0(n)w.sub.0(p). This weight vector is then stored in memory [20], allowing its use as an initial combiner weight vector in a subsequent adapt block. The weight vector can also be used in a port p data-path linear combiner (not shown) for parallel or subsequent data-path processing operations used in the overall system.

[0052] FIG. 6 is a view of a nonblind, multiport, fully-coupled SCPU adapt path weight update method, depicting use of projection matrices (implemented using simple multiplexing and demultiplexing operations) to separate data and weights into unconstrained and subspace-constrained components, allowing use of an unconstrained multiport weight adaptation algorithm of arbitrary type and structure after the subspace separation procedure. Over adapt block n, the N×M data matrix X(n) provided by the 1:N S/P bank [2] (not shown) is separated into an N×M.sub.1 dimensional update-set data matrix X.sub.1(n)=X(n)M.sub.1(n) and an N×M.sub.0 dimensional held-set data matrix X.sub.0(n)=X(n)M.sub.0(n), using a columnar matrix demultiplexer (DMX) [11] and the update-set and held-set projection matrices provided over adapt block n from the update-set selection algorithm [7]. The M×M.sub.0 dimensional held-set projection matrix M.sub.0(n) is additionally used to extract the M.sub.0×P dimensional held-set combiner weights W.sub.0=M.sub.0.sup.T(n)W from the M×P dimensional combiner weight matrix W stored in current memory [20], e.g., computed over a prior adapt block, using a held-set multiport weight extractor [22]. The held-set data matrix X.sub.0(n) is then multiplied by the M.sub.0×P held-set multiport combiner weights W.sub.0 through a linear combiner [23], yielding N×P multiport held-set output data vector Y.sub.0(n)=X.sub.0(n)W.sub.0. X.sub.1(n) and Y.sub.0(n) are then combined into an N×(M.sub.1+P) dimensional enhanced data matrix {tilde over (X)}(n)=[X.sub.1(n) Y.sub.0(n)] using a column-wise multiplexing (MUX) operation [24].

[0053] The enhanced data matrix is then input to an unconstrained multiport weight adaptation algorithm [25] that adjusts every element of (M.sub.1+P)×P enhanced multiport combiner matrix {tilde over (W)}(p)=

[00003] $(\begin{matrix} W_{1} \\ G_{0} \end{matrix})$

to optimize a metric of similarity between an N×P reference vector S(n) provided by a multiport reference generator (not shown) and an N×P output data matrix Y(n)={tilde over (X)}(n){tilde over (W)} that would be provided by an (M.sub.1+P)×P element linear combining operation (not shown), e.g., the sum-of-squares error metric F({tilde over (W)}; n)=∥S(n)−{tilde over (X)}((n){tilde over (W)}∥.sub.F.sup.2, where ∥•∥.sub.F denotes the Frobenius matrix norm. However, the complexity of the unconstrained weight adaptation algorithm is O(P(M.sub.1+1).sup.v) in [25], where v is the complexity order of the algorithm, e.g., v=2 if a sum-of-squares metric is used to optimize {tilde over (W)}.

[0054] The updated (M.sub.1+P)×P dimensional enhanced combiner vector {tilde over (W)} is then demultiplexed (DMX'd) [26] into an updated M.sub.1×P dimensional update-set weight matrix W.sub.1 comprising the first M.sub.1 rows of {tilde over (W)}, and a new P×P dimensional held-set multiplier matrix G.sub.0 comprising the last P rows of {tilde over (W)}. The held-set multiplier matrix G.sub.0 is then multiplied by the current M.sub.0×P held-set weights W.sub.0 [27] to form updated held-set weights W.sub.0←W.sub.0G.sub.0, and multiplexed (MUX'd) [28] with the updated M.sub.1×P update-set weight vector W.sub.1, in accordance with the current update-set selection algorithm [7], to form updated M×P dimensional weight matrix W=M.sub.1(n)W+M.sub.0(n)W.sub.0. This weight matrix is then stored in memory [20], allowing its use as an initial combiner weight matrix in a subsequent adapt block. The weight matrix can also be used in a multiport data-path linear combiner (not shown) for parallel or subsequent data-path processing operations used in the overall system.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0055] A method for processing digital signals by any adaptive processor (as a single element or set of interacting elements, and whether entirely embodied in physical hardware or in a combined form of hardware, special-purpose firmware, and general processing purpose software applied to effect digital signal processing) that adjusts signal weights on the digital signal(s) transmitted, received, or both, by or through said adaptive processor, in order to optimize an adaptation criteria responsive to a functional purpose or the externalities (transient, temporary, situational, and even permanent) for that processor, is explained. This adaptation criteria for the adaptive algorithm may be any of a signal or parameter estimation, measured quality, or any combination thereof.

[0056] This method performs a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event, where M.sub.1<<M and L<<M such that M.sub.1 weights are updated without constraints and M.sub.0=M−M.sub.1 weights are subjected to a soft constraints that forces them into an L-dimensional subspace spanned by the those weights at the beginning of the adaptation period. The same dimensionality reduction, using the same linear transformation, is applied to the input data. The reduced-dimensionality weights are then adapted using the same optimization strategy employed by the adaptive processor, except with input data that has also been reduced in dimensionality. In a preferred embodiment the reduced-dimensionality weights are then adapted using exactly the same optimization strategy. In alternative embodiment, as when there exists any of hardware, software, or combined hardware and software differentiation in “adapt-path” operations used to tune the adaptive processor and “data-path” operations used by the adaptive processor during and after tuning, the method will be adapting the reduced-dimensionality weights using substantively the same optimization strategy employed by the adaptive processor for the input data to which the same dimensionality reduction has been applied.

[0057] The invention has numerous advantages over the conventional PU approach. These include: [0058] Substantive reduction or elimination of misadjustment effects induced by the hard linear constraint employed in the conventional PU method. [0059] Applicability to any optimization function, including functions based on optimal (maximum-likelihood, maximum a priori, minimum-mean-square) estimation strategies, and methods such as analytic constant modulus algorithm (ACMA) and cumulant based techniques that have very high-order complexity. [0060] Ability to reduce adapt block size N significantly, e.g., to N<M, even when the unconstrained approach experiences instability issues at that block size. [0061] Ability to develop optimization quality measures, e.g., Cramer-Rao bound on parameter or signal estimation performance, that also exploits the dimensionality reduction, and that can track the performance degradation (relative to the unconstrained solution) induced by the partial update. [0062] Ability to operate with much lower update set sizes that conventional PU, resulting in further reduction in complexity, and therefore cost, of adapt-path processing. [0063] Ability to be implemented in highly distributed processing architectures, e.g., general-purpose graphical processing units (GPGPU's), that can further exploit the reduced complexity of the approach, or allow processing over multiple parallel update sets with minimal intercommunication between units. [0064] Applicability to other problems where dimensionality is a known limitation, e.g., pattern recognition over feature sets with large numbers of parameters.

[0065] The approach can be used with any update-set selection strategy developed to date, or with new methods exploiting quality measurement advantages of the approach.

[0066] The invention is motivated by interpreting prior-art partial-update approaches as hard-constrained optimization algorithms, in which a complex combiner weight vector w having dimension M×1 is updated to optimize metric F(w;n) over adapt block n, i.e.,

[00004] $\begin{matrix} w \leftarrow \arg .Math. .Math. \underset{w^{'} \in C^{M}}{opt} .Math. .Math. F (w^{'}; n), & (Eq1) \end{matrix}$

subject to additional linear constraint

(w′ custom-character .sub.(n)=(w.sub.(n), (Eq2)

where custom-character .sub.0(n)={m∈{1, . . . , M}: m(1;n), . . . , m(M.sub.0;n)}, referred to here as the block n held-set, is a set of M.sub.0<M indices of weights held constant over adapt block n, and where w in (Eq2) is the combiner weights at the beginning of the adapt block. This resultant constrained optimization criterion can be written in compact matrix algebra as

[00005] $\begin{matrix} w \leftarrow \arg .Math. .Math. \underset{w^{'} \in C^{M}}{opt} .Math. .Math. {F (w^{'}; n) .Math. M_{0} (n) .Math. w^{'} = M_{0} (n) .Math. w} & (Eq3) \end{matrix}$

where M.sub.0(n)=[e.sub.M(m.sub.0) custom-character .sub.(n) is the M×M.sub.0 sparse held-set projection matrix, and where e.sub.M (m.sub.0)=[δ(m−m.sub.0)].sub.m=1.sup.M is the m.sub.0.sup.th M×1 Euclidean basis vector and δ(k) is the Kronecker delta function. Example prior-art partial-update algorithms that can be expressed in this manner include: [0067] The partial-update normalized least-mean-squares (PU-NLMS) algorithm, which modifies the normalized least-mean-squares (NLMS) algorithm taught in [Nagumo67]

[00006] $\begin{matrix} y (n) = x^{T} (n) .Math. w, & (Eq4) \\ w \leftarrow w + μ .Math. \frac{x^{*} (n)}{{.Math. x (n) .Math.}_{2}^{2}} .Math. (s (n) - y (n)), 0 < μ \leq 1 & (Eq5) \\ = \arg .Math. .Math. \min_{w^{'} \in C^{M}} .Math. {.Math. w^{'} - w .Math.}_{2}^{2} .Math. x^{T} (n) .Math. w^{'} = \hat{s} (n) & (Eq6) \\ \hat{s} (n) = μ .Math. .Math. s (n) + (1 - μ) .Math. y (n), 0 < μ \leq 1 & (Eq7) \end{matrix}$ at adapt symbol index n, where x(n) is an M×1 data vector defined over adapt symbol index n, s(n) is a reference scalar known over adapt symbol index n.sub.sym, μ is the NLMS adaptive stepsize, and ∥•∥.sub.2 is the L-2 norm, and where (•).sup.T and (•)* denote the matrix transpose and complex conjugation operations, respectively. Addition of the held-set weight-update constraint

M.sub.0(n)w′=M.sub.0(n)w, (Eq8) to (Eq6) yields the PU-NLMS algorithm taught in [Douglas94,Schertler98,Dogancay01],

[00007] $\begin{matrix} y (n) = x^{T} (n) .Math. w, & (Eq9) \\ w_{} = M_{}^{T} (n) .Math. w,  = 0, 1 & (Eq10) \\ x_{} = M_{}^{T} (n) .Math. x (n),  = 0, 1 & (Eq11) \\ w_{1} \leftarrow w_{1} + μ .Math. \frac{x_{1}^{*} (n)}{{.Math. x (n) .Math.}_{2}^{2}} .Math. (s (n) - y (n)), 0 < μ \leq 1, & (Eq12) \\ w \leftarrow M_{1} (n) .Math. w_{1} + M_{0} (n) .Math. w_{0} & (Eq13) \end{matrix}$ [0068] where M.sub.1(n)=[e.sub.M(m.sub.1) custom-character .sub.(n) is the M×M.sub.1 update-set projection matrix defined over adapt symbol n, and where .sub.1(n)={m∈{1, . . . , M}: m.Math..sub.0(n)} is the complementary update-set defined over adapt symbol n. [0069] The partial-update affine projections (PU-AP) algorithm, which modifies the affine projection algorithm taught in [Ozeki84,Gay93]

[00008] $\begin{matrix} y (n) = X (n) .Math. w, & (Eq14) \\ w \leftarrow w + μ .Math. .Math. X^{†} (n) .Math. (s (n) - y (n)), 0 < μ \leq 1, & (Eq15) \\ = \arg .Math. .Math. \min_{w^{'} \in C^{M}} .Math. {.Math. w^{'} - w .Math.}_{2}^{2} .Math. X (n) .Math. w^{'} = \hat{s} (n), & (Eq16) \\ \hat{s} (n) = μ .Math. .Math. s (n) + (1 - μ) .Math. y (n), 0 < μ \leq 1 & (Eq17) \end{matrix}$ over N-symbol adapt block n, 1≦N≦M, where X(n)=[x(nN+1) . . . x(nN+N)].sup.T is an N×M data matrix defined over adapt block n, s(n)=[s(nN+1) . . . s(nN+N)].sup.T is a known N×1 reference vector defined over adapt block n, μ is an adaptive stepsize, and (•).sup.† denotes the matrix pseudoinverse operation, given by

X.sup.†(n)=X.sup.H(n)(X(n)X.sup.H(n)).sup.−1, (Eq18) for rank{X(n)}=N≦M, and where (•).sup.H and (•).sup.−1 denote the matrix conjugate-tranpose (Hermitian) and inverse operations, respectively. Addition of constraint (Eq8) to (Eq16) yields the PU-AP taught in [Naylor04],

y(n)=X(n)w, (Eq19)

w.sub.l=M.sub.l.sup.T(n)w, l=0,1, (Eq20)

X.sub.l(n)=X(n)M.sub.l(n), l=0,1, (Eq21)

w.sub.1←w.sub.1+μX.sub.1.sup.†(n)(s(n)−y(n)), 0<μ≦1, (Eq22)

w←M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0. (Eq23) [0070] The partial-update block least-squares (PU-BLS) algorithm, which modifies the block least-squares (BLS) algorithm given by

[00009] $\begin{matrix} y (n) = X (n) .Math. w, & (Eq24) \\ w \leftarrow (1 - μ) .Math. w + μ .Math. .Math. X^{†} (n) .Math. s (n), & (Eq25) \\ = \arg .Math. .Math. \min_{w^{'} \in C^{M}} .Math. {.Math. s^{'} (n) - X (n) .Math. w^{'} .Math.}_{2}^{2}, .Math. {\begin{matrix} \hat{s} (n) = μ .Math. .Math. \hat{s} (n) + (1 - μ) .Math. y (n) \\ y (n) = X (n) .Math. w \end{matrix} & (Eq26) \end{matrix}$ over N-symbol adapt block n, N≧M, where ∥•∥.sub.2 is the L-2 norm and μ is the AP adaptive stepsize, and where X(n)=[x(nN+1) . . . x(nN+N)].sup.T is an N×M data matrix defined over adapt block n, s(n)=[s(nN+1) . . . s(nN+N)].sup.T is a known N×1 reference vector defined over adapt block n, and (•).sup.† denotes the matrix pseudoinverse operation, given by

X.sup.†(n)=(X.sup.H(n)X(n)).sup.−1X.sup.H(n) (Eq27) for rank{X(n)}=M≦N. Addition of constraint (Eq8) to (Eq26) yields PU-BLS algorithm

y(n)=X(n)w, (Eq28)

w.sub.l=M.sub.l.sup.T(n)w, l=0,1, (Eq29)

X.sub.l(n)=X(n)M.sub.l(n), l=0,1, (Eq30)

w.sub.1←(1−μ)w.sub.1+μX.sub.1.sup.†(n)(s(n)−y(n)), 0<μ≦1, (Eq31)

w←M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0. (Eq32)

[0071] The BLS and PU-BLS algorithms can be interpreted as extensions of the AP and PU-AP algorithms to adapt block sizes N≧M. Similarly, the NLMS and PU-NLMS algorithms can be interpreted as implementations of the AP and PU-AP algorithms for N=1.

[0072] A number of observations can immediately be made from this interpretation of the partial-update procedure. First, any linear constraint can induce severe misadjustment from the optimal solution sought by the processor. This can manifest as both a convergent or steady-state bias from the optimal solution, and a “jitter” or fluctuation about that steady-state solution. In some applications, e.g., phased array radar applications where the received radar waveform must be extracted from strong clutter and jamming, this can cause the system to fail entirely. Even if the reference signal is received at high SINR, this can lead to well-known “hypersensitivity” issues that degrade system performance from the optimal solution.

[0073] Second, the linear constraint can only be easily added to a small subset of optimization functions. In many cases, strict enforcement of the constraint significantly increases complexity of the original method.

[0074] The subspace-constrained approach overcomes both of these problems, by replacing the hard linear constraint M.sub.0(n)w′=M.sub.0(n)w with a softer subspace constraint

M.sub.0.sup.T(n)w′∝M.sub.0.sup.T(n)w

=M.sub.0.sup.T(n)wg.sub.0, g.sub.0∈ custom-character , (Eq33)

where the scalar held-set multiplier g.sub.0 and the update-set weights w.sub.1=M.sub.1(n)w are jointly adjusted to optimize the unconstrained criterion given in (Eq1), i.e., by adapting (M.sub.1+1)×1 enhanced weight vector

[00010] $\tilde{w} = (\begin{matrix} w_{1} \\ g_{0} \end{matrix})$

using optimization formula

[00011] $\begin{matrix} \tilde{w} \leftarrow \arg .Math. .Math. \underset{{\tilde{w}}^{'} \in ℂ^{M_{1} + 1}}{opt} .Math. F ({\tilde{w}}^{'}; n) & (Eq .Math. .Math. 34) \end{matrix}$

over each data block. The full output weight vector is then given by

w=M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0g.sub.0, (Eq35) [0075] which is efficiently computed using vector-scalar multiplies and multiply-free multiplexing (MUX) operations.

[0076] For the exemplary NLMS, AP, and BLS optimization criteria given in (Eq6), (Eq16), and (Eq26), respectively, the SCPU algorithms are implemented using the following procedure: [0077] Separate w into update-set and held-set components w.sub.1 and w.sub.0 using multiply-free demultiplexing (DMX) operations. [0078] For the SCPU-AP/NLMS algorithms, and for the SCPU-BLS algorithm with μ<1, construct (M.sub.1+1)×1 dimensional weight matrix

[00012] $\begin{matrix} \tilde{w} = (\begin{matrix} w_{1} \\ 1 \end{matrix}) . & (Eq .Math. .Math. 36) \end{matrix}$ [0079] Separate X(n) into update-set and held-set components X.sub.1(n) and X.sub.0(n) using multiply-free columnar DMX operations. [0080] Compute y.sub.0(n)=X.sub.0(n)w.sub.0. For the SCPU-AP/NLMS algorithms, further compute y.sub.1(n)=X.sub.1(n)w.sub.1 and y(n)=y.sub.1(n)+y.sub.0(n). [0081] Construct N×(M.sub.1+1) dimensional SCPU data matrix

{tilde over (X)}(n)=[X.sub.1(n)y.sub.0(n)]. (Eq37) Note that y(n)={tilde over (X)}(n){tilde over (w)} constructs the output data from the prior weight set. [0082] Optimize {tilde over (w)} using the original unconstrained algorithm, with dimensionality reduced from M to M.sub.1+1, yielding

SCPU-AP: {tilde over (w)}←{tilde over (w)}+μ{tilde over (X)}.sup.†(n)(s(n)−y(n)), 0<μ≦1 (Eq38)

SCPU-BLS: {tilde over (w)}←(1−μ){tilde over (w)}+μ{tilde over (X)}.sup.†(n)s(n), 0<μ≦1, (Eq39) where the SCPU-AP algorithm degenerates to SCPU-NLMS if N=1, and extends to SCPU-BLS if N≧M.sub.1. [0083] Update w.sub.1 and w.sub.0 using formula

w.sub.1←[({tilde over (w)}).sub.m].sub.m=1.sup.M.sup.1 (Eq40)

w.sub.0←g.sub.0w.sub.0, g.sub.0=({tilde over (w)}).sub.M.sub.1.sub.+1, (Eq41) where ({tilde over (w)}).sub.m denotes the m.sup.th element of vector {tilde over (w)}. [0084] Reconstruct the linear combiner weights using.

w=M.sub.1(n)w.sub.1+M.sub.0(n)w.sub.0. (Eq42)

[0085] The SCPU approach employs a data matrix with a nominal dimensionality increase of one over the equivalent PU data matrix, and requires an additional M.sub.0 complex multiplies to update the held-set weight vector. This complexity increase is substantive for the PU-NLMS algorithm, which has O(M) complexity on the data path and O(M.sub.1) complexity on the adapt path. However, this complexity increase is minor for the PU-BLS algorithm, which has O(M.sub.1.sup.2) complexity on the adapt path, and for the PU-AP algorithm if the adapt block size N is less than but on the order of the number of updated weights M.sub.1 (N≲M.sub.1). Because the SCPU approach optimizes g.sub.0=({tilde over (w)}).sub.M.sub.1.sub.+1 over the complex field, the algorithm is also guaranteed to have lower misadjustment than the equivalent PU method, which constrains g.sub.0 to unity.

[0086] This implementation of a SCPU algorithm obtains a higher degree of efficiency (in comparison with either an unconstrained partial update, or full update algorithm) through reducing the level of repetitive processing and comparison which is needed to obtain the maximally-beneficial level, and mixture, of signal weightings that, when applied to the next processing effort, will produce the correct answer within the noise constraints. If applied so as to remove arbitrarily-imposed limits on either the processing depth, or on the number of criteria to be evaluated, then a satisficing level of accuracy can be reached without sacrificing the capacities which were otherwise artificially constrained. Since the weighting dimensionality is reduced by and to the level of the constraints on the subspace, without changing the data path, the efficiency of the transforming process is improved over the full analytical processing effort.

[0087] The SCPU algorithm employs a data matrix with a nominal dimensionality increase of one over the equivalent partial-update (PU) data matrix, and which employs an additional O(M.sub.0) complex scalar-vector multiplier to update the held-set weight vector. This can be expressed in the following compact matrix notation:

[00013] $\begin{matrix} \tilde{M} (n) = [\begin{matrix} M_{1} (n) & M_{0} (n) .Math. M_{0}^{T} (n) .Math. w \end{matrix}] & (Eq .Math. .Math. 43) \\ \tilde{x} (n) = X (n) .Math. \tilde{M} (n) & (Eq .Math. .Math. 44) \\ \tilde{w} = \arg .Math. .Math. \underset{\tilde{w} \in ℂ^{M_{1} + 1}}{opt} .Math. F (\tilde{w}; n) & (Eq .Math. .Math. 45) \\ y (n) = \tilde{X} (n) .Math. \tilde{w} & (Eq .Math. .Math. 46) \\ w \leftarrow \tilde{M} (n) .Math. \tilde{w}, & (Eq .Math. .Math. 47) \end{matrix}$

where {tilde over (M)}(n) is an M×(M.sub.1+1) sparse mapping matrix than reduces dimensionality of X(n) ahead of the optimization algorithm described symbolically in (Eq45).

[0088] This compact notation reveals some additional advantages of the approach: [0089] The approach is inherently more stable than the unconstrained algorithm on a block-by-block basis, because it updates fewer weights than the unconstrained method, without introducing explicit hard constraints that lead to adaptive “jitter.” Hypersensitivity effects due to large noise subspaces in the received data should be especially reduced in the SCPU method. [0090] The approach is usable with any optimization criterion, including non-quadratic criteria such as general and analytic constant modulus cost functions [Treichler83,Agee86,Van Der Veen 96], cumulant based objective functions, and eigenvalue-based objective functions [Agee89b,Agee90]. [0091] The approach admits both SCPU maximum-likelihood signal and parameter estimation approaches, and reduced-complexity, constrained quality metrics such as signal-to-interference-and-noise ratio (SINR), Cramer-Rao bounds on parameter estimates, and information-theoretic channel capacity. These metrics may lead to new update-set selection strategies that can overcome identified issues with methods developed to date.

[0092] The mapping given in (Eq43) can be extended in many ways to enhance other attributes of the algorithm, e.g., ability to track multiple signals, new selection strategies, and so on. In particular, the approach immediately yields nonblind multipart extensions in which adaptation algorithms are used to extract multiple signals from a received environment.

[0093] Two multipart extensions of the AP and BLS methods are taught here based on the unconstrained nonblind algorithms given by

AP: W←W+μX.sup.†(n)(S(n)−Y(n)), 0<μ≦1 (Eq48)

BLS: W←(1−μ)W+μX.sup.†(n)S(n), 0<μ≦1, (Eq49)

where W is an M×P combiner matrix, Y(n)=X(n)W is an N×P matrix of combiner output data formed over adapt block n using W, and S(n) is an N×P matrix of reference data known over adapt block n. These multipart extensions include the following: [0094] An uncoupled multiport extension in which (Eq43) is replaced by P separate mapping matrices

{tilde over (M)}(n;p)=[M.sub.1(n)M.sub.0(n)M.sub.0.sup.T(n)w(p)], p=1, . . . ,P, (Eq50)

{tilde over (X)}(n;p)=X(n){tilde over (M)}(n;p), p=1, . . . ,P, (Eq51) i.e., the SCPU constraint (Eq33) is broadened to P separate constraints

M.sub.0.sup.T(n){tilde over (w)}(p)=M.sub.0.sup.T(n)w(p)g.sub.0(p), g.sub.0(p)∈ custom-character , p=1, . . . ,P. (Eq52) The uncoupled SCPU-BLS algorithm is then given by

[00014] $\begin{matrix} \tilde{X} (n; p) = X (n) .Math. \tilde{M} (n; p) & (Eq .Math. .Math. 53) \\ \tilde{w} (p) = (\begin{matrix} M_{1}^{T} (n) .Math. w (p) \\ 1 \end{matrix}) & (Eq .Math. .Math. 54) \\ \tilde{w} (p) \leftarrow (1 - μ) .Math. \tilde{w} (p) + μ .Math. .Math. {\tilde{X}}^{†} (n; p) .Math. s (n; p), .Math. 0 \leq μ \leq 1 & (Eq .Math. .Math. 55) \\ y (n; p) = \tilde{X} (n; p) .Math. \tilde{w} (p) & (Eq .Math. .Math. 56) \\ w (p) \leftarrow \tilde{M} (n; p) .Math. \tilde{w} (p) & (Eq .Math. .Math. 57) \end{matrix}$ for each port p=1, . . . , P where s(n;p) and w(p) are the p.sup.th column of S(n) and W, respectively, and where (Eq54) is only needed if μ<1. [0095] A fully-coupled multiport extension, in which (Eq43) is replaced by global mapping matrix

{tilde over (M)}(n)=[M.sub.1(n)M.sub.0(n)M.sub.0.sup.T(n)W], (Eq58) i.e., the SCPU constraint (Eq33) is broadened to

M.sub.0.sup.T(n)W′=M.sub.0.sup.T(n)WG.sub.0, G.sub.0∈ custom-character .sup.P×P. (Eq59) The fully-coupled SCPU-BLS algorithm is then given by

[00015] $\begin{matrix} \tilde{X} (n) = X (n) .Math. \tilde{M} (n), & (Eq .Math. .Math. 60) \\ \tilde{W} = (\begin{matrix} M_{1}^{T} (n) .Math. W \\ I_{P} \end{matrix}) & (Eq .Math. .Math. 61) \\ \tilde{W} \leftarrow (1 - μ) .Math. \tilde{W} + μ .Math. .Math. {\tilde{X}}^{†} (n) .Math. S (n), .Math. 0 < μ \leq 1 & (Eq .Math. .Math. 62) \\ Y (n) = \tilde{X} (n) .Math. \tilde{W} & (Eq .Math. .Math. 63) \\ W \leftarrow \tilde{M} (n) .Math. \tilde{W}, & (Eq .Math. .Math. 64) \end{matrix}$

and where (Eq61) is only needed if μ<1.

[0096] In an efficient embodiment, the uncoupled multiport SCPU-BLS extension is implemented using whitening methods that exploit the common components of {{tilde over (X)}(n;p)}.sub.p=1.sup.P, i.e., the N×M.sub.1 dimensional update-set data matrix X.sub.1(n)=X(n)M.sub.1(n).

[0097] In particular, using the QR decomposition of {tilde over (X)}(n;p), given by

[00016] $\begin{matrix} {Q, R} = QRD (X), .Math. {\begin{matrix} R = chol .Math. {X^{H} .Math. X} \\ Q = {XR}^{- 1} \end{matrix} & (Eq .Math. .Math. 65) \\ .Math. {\begin{matrix} X = QR \\ Q^{H} .Math. Q = I_{N} \end{matrix} & (Eq .Math. .Math. 66) \end{matrix}$

for general N×M matrix X with rank{X}=N≧M, where I.sub.N is the N×N identity matrix and chol{•} is the Cholesky decomposition yielding upper-triangular matrix R with real-positive diagonal values, then the upcoupled multiport SCPU-BLS algorithm given in (Eq55) can be efficiently implemented by first computing the QRD of the common update-set data matrix,

{Q.sub.1,R.sub.11}=QRD(X.sub.1(n)), (Eq67)

and then updating each port p using the recursion

[00017] $\begin{matrix} y_{0} \leftarrow X_{0} (n) .Math. w_{0} (p) & (Eq .Math. .Math. 68) \\ r_{10} \leftarrow Q_{1}^{H} .Math. y_{0} & (Eq .Math. .Math. 69) \\ u_{1} \leftarrow Q_{1}^{H} .Math. s (n; p) & (Eq .Math. .Math. 70) \\ g_{0} (p) \leftarrow \frac{y_{0}^{H} .Math. s (n; p) - r_{10}^{H} .Math. u_{1}}{{.Math. y_{0} .Math.}_{2}^{2} - {.Math. r_{10} .Math.}_{2}^{2}} & (Eq .Math. .Math. 71) \\ w_{1} (p) \leftarrow (1 - μ) .Math. w_{1} (p) + μ .Math. .Math. R_{11}^{- 1} (u_{1} - r_{10} .Math. g_{0} (p)), .Math. 0 < μ \leq 1 & (Eq .Math. .Math. 72) \\ g_{0} (p) \leftarrow (1 - μ) + μ .Math. .Math. g_{0} (p), .Math. 0 < μ \leq 1 & (Eq .Math. .Math. 73) \end{matrix}$

where

[00018] $\tilde{w} (p) = (\begin{matrix} w_{1} (p) \\ g_{0} (p) \end{matrix}) .$

This recursion also admits unbiased quality statistic

[00019] $\begin{matrix} {\tilde{γ}}_{\max} (n; p) = (1 - \frac{M_{1} + 1}{N}) .Math. (\frac{\tilde{η}}{1 - \tilde{η}}) - \frac{M_{1} + 1}{N}, .Math. \tilde{η} = \frac{{.Math. u_{1} .Math.}_{2}^{2} + {.Math. u_{0} .Math.}_{2}^{2}}{{.Math. s (n; p) .Math.}_{2}^{2}} & (Eq .Math. .Math. 74) \end{matrix}$

for each port p, which estimates the relative power between the port p reference signal and background clutter at the output of the port p linear combiner, also referred to as the signal-and-interference-and-noise ratio (SINR) of the combiner output signal.

[0098] The SCPU method is also easily extended to partially blind methods in which the reference vector s(n) is partially known at the receive processor over adapt block n, e.g., the reference vector has an unknown carrier or timing offset relative to the sequence contained in the input data sequence, and to fully blind methods in which the reference vector is unknown but has some known, exploitable structure. Specific examples include: [0099] Carrier-timing tracking SCPU-BLS algorithms, in which s(n) has an unknown timing and/or carrier offset, e.g., due to propagation delay, Doppler shift and carrier LO uncertainty between the input data and an original transmitted signal containing the reference signal, or a combined frequency shift due to timing and carrier offset if the input data is derived from an OFDM or OFDMA demodulation process. This algorithm replaces the nonblind weight adaptation algorithm given in (Eq39) with

{tilde over (w)}←(1−μ){tilde over (w)}+μ{tilde over (X)}.sup.†(n)(s({circumflex over (n)}.sub.off;n)∘δ({circumflex over (ω)}.sub.off)) (Eq75)

s(n.sub.off;n)=[s(nN+n.sub.sym+n.sub.off).sub.n.sub.sym.sub.=1.sup.N] (Eq76)

δ(ω.sub.off)=[e.sup.jω.sup.off.sup.n.sup.sym].sub.n.sub.sym.sub.=1.sup.N (Eq77) where {s(n.sub.sym)} is a component of the transmitted signal that is known over the adapt block except for timing offset n.sub.off and a carrier offset ω.sub.off, and where “∘” is the element-wise matrix multiplication operation. The timing and carrier offset can be optimized over each adapt block by setting

[00020] $\begin{matrix} .Math. {{\hat{ω}}_{off} (n), {\hat{n}}_{off} (n)} = \arg .Math. \max_{ω_{off}, n_{off}} .Math. η (ω_{off}, n_{off}; n), & (Eq .Math. .Math. 78) \\ \begin{matrix} η (ω_{off}, n_{off}; n) = .Math. \frac{{.Math. {\tilde{Q}}^{H} (n) .Math. (s (n_{off}; n) .Math. •δ (ω_{off})) .Math.}_{2}^{2}}{{.Math. s (n_{off}; n) .Math.}_{2}^{2}}, \\ = .Math. \frac{{.Math. {.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {\tilde{q}}^{*} (n_{sym}) .Math. s (\begin{matrix} nN + \\ n_{sym} + \\ n_{off} \end{matrix}) .Math. e^{{jω}_{off} .Math. n_{sym}} .Math.}_{2}^{2}}{{.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {.Math. s (nN + n_{sym} + n_{off}) .Math.}^{2}}, (Eq .Math. .Math. 80) \end{matrix} & (Eq .Math. .Math. 79) \end{matrix}$ where {tilde over (Q)}=[{tilde over (q)}(1) . . . {tilde over (q)}(N)].sup.T is the Q-component of the QRD of {tilde over (X)}(n). Equation (Eq78) can be efficiently implemented using fast Fourier transform (FFT) methods if the frequency offset ω is completely unknown (acquisition phases), and using Gauss-Newton or Newton methods if the frequency offset ω is known closely (tracking phases). Equation (Eq78) also admits quality statistic

[00021] $\begin{matrix} \tilde{γ} (ω_{off}, n_{off}; n) = (1 - \frac{M_{1} + 1}{N}) .Math. (\frac{\tilde{η} (ω_{off}, n_{off}; n)}{1 - \tilde{η} (ω_{off}, n_{off}; n)}) - \frac{M_{1} + 1}{N}, & (Eq .Math. .Math. 81) \end{matrix}$ which estimates the SINR of the combiner output signal. [0100] Property-mapping SCPU-BLS algorithms, in which s(n) is a member of a known property set. These algorithms replace the nonblind weight adaptation algorithm given in (Eq39) with property-mapping recursion

[00022] $\begin{matrix} y (n) = \tilde{X} (n) .Math. \tilde{w} & (Eq .Math. .Math. 82) \\ \hat{s} (n) = \arg .Math. \min_{s \in  (n)} .Math. .Math. s - y (n) .Math. & (Eq .Math. .Math. 83) \\ \tilde{w} \leftarrow (1 - μ) .Math. \tilde{w} + μ .Math. .Math. {\tilde{X}}^{†} (n) .Math. \hat{s} (n), & (Eq .Math. .Math. 84) \end{matrix}$ [0101] where custom-character (n) is a desired signal set, potentially variable as a function of adapt block n, that s(n) is known to belong to. For example, the constant modulus property set: (n)={z∈.sup.N:|(z).sub.n|=1} yields

{circumflex over (s)}(n)=sgn{y(n)} (Eq85) where sgn{•} is the element-wise complex sign function sgn{z}=z/|z| on each element, resulting in an SCPU-BLS constant-modulus algorithm. Other exemplary mappings include known modulus mappings in which the elements of s(n) have known magnitude but unknown phase, and decision-direction mappings in which each element of s(n) belongs to a known set of finite values, possibly with an unknown carrier offset. In all cases, the property-mapping algorithm is applicable to cases in which s(n) does not perfectly possess the property used by the algorithm, but substantively conforms to that property, e.g., |s(nN+n.sub.sym)|≈1. [0102] Dominant-mode prediction (DMP) algorithms, in which s(n) is known to be substantively present in a linear subspace with known or estimable structure, such that

s(n)≈(U.sub.s(n)U.sub.s.sup.H(n))s(n) (Eq86) for a known or postulated N×N.sub.s(n) orthonormal basis U.sub.s(n), N.sub.s(n)<N, and/or such that s(n) is known to be substantively absent a linear subspace with known or estimable structure, such that

U.sub.⊥.sup.H(n)s(n)≈0 (Eq87) for a known or postulated complementary N×N.sub.⊥(n) orthonormal basis U.sub.⊥(n), in which N.sub.s(n)+N.sub.⊥(n)≦N. If only one subspace is available, one can be derived from the other, for example by deriving U.sub.⊥(n) from I.sub.N−(U.sub.s(n)U.sub.s.sup.H(n)) or vice verse. In this case, the enhanced weight update algorithm is given by

[00023] $\begin{matrix} \tilde{w} = \arg .Math. \max_{w \in ℂ^{M_{1} + 1}} .Math. \tilde{γ} (w; n), & (Eq .Math. .Math. 88) \\ \tilde{γ} (w; n) = \frac{w^{H} ({\tilde{X}}_{s}^{H} (n) .Math. {\tilde{X}}_{s} (n)) .Math. w}{w^{H} ({\tilde{X}}_{⊥}^{H} (n) .Math. {\tilde{X}}_{⊥} (n)) .Math. w}, .Math. {\begin{matrix} {\tilde{X}}_{s} (n) = U_{s}^{H} (n) .Math. \tilde{X} (n) \\ {\tilde{X}}_{⊥} (n) = U_{⊥}^{H} (n) .Math. \tilde{X} (n) \end{matrix} . & (Eq .Math. .Math. 89) \end{matrix}$ The enhanced combiner weights {tilde over (w)}.sub.max that maximize (Eq89), and the maximal value of (Eq89), {tilde over (γ)}.sub.max, are equal to the dominant solution {{tilde over (γ)}.sub.1,{tilde over (w)}.sub.1} of the DMP eigenequation,

{tilde over (γ)}.sub.m({tilde over (X)}.sub.⊥.sup.H(n){tilde over (X)}.sub.⊥(n)){tilde over (w)}.sub.m=({tilde over (X)}.sub.s.sup.H(n){tilde over (X)}.sub.s(n)){tilde over (w)}.sub.m, {tilde over (γ)}.sub.m≧{tilde over (γ)}.sub.m+1. (Eq90) The dominant eigenvalue {tilde over (γ)}.sub.1 also provides an estimate of the SINR of the combiner output signal, and can be used both to detect the target signal, and to search over postulated subspaces to find the subspace that most closely contains or rejects s(n). Example subspaces include: [0103] Known or postulated time slots used by s(n), such that

[00024] $.Math. s (nN - n_{sym}) .Math.  \frac{1}{N} .Math. {.Math. s (n) .Math.}_{2}$ over some known or searchable subset of symbol indices within the adapt block. This generates SCPU time-gated DMP (TG-DMP) algorithms. [0104] Known or postulated frequency channels used by s(n), such that

[00025] $\begin{matrix} \frac{{.Math. {.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. h (n_{sym}) .Math. s (nN + n_{sym}) .Math. e^{- jω .Math. .Math. n_{sym}} .Math.}^{2}}{{.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. h^{2} (n_{sym}) .Math. {.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. h (n_{sym}) .Math. {.Math. s (nN + n_{sym}) .Math.}^{2}}  1 & (Eq .Math. .Math. 91) \end{matrix}$ over a known or searchable subset of frequency offsets {ω.sub.⊥}, where {h(n.sub.sym)}.sub.n.sub.sym.sub.=1.sup.N is a lowpass windowing function, e.g., a Gaussian or Hamming window. This generates SCPU frequency-gated DMP (FG-DMP) algorithms. [0105] Known or postulated CDMA codes used by s(n), such that

[00026] $\begin{matrix} \frac{{.Math. {.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. c^{*} (n_{sym} - n_{off}) .Math. s (nN + n_{sym}) .Math. e^{- {jω}_{off} .Math. n_{sym}} .Math.}^{2}}{{.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. {.Math. c (n_{sym} - n_{off}) .Math.}^{2} .Math. {.Math.}_{n_{sym} = 1}^{N - 1} .Math. .Math. {.Math. s (nN - n_{sym}) .Math.}^{2}} \approx 1 & (Eq .Math. .Math. 92) \end{matrix}$ over a known or searchable subset of carrier offsets to {ω.sub.off} and timing offsets {n.sub.off}, where {c(n.sub.sym)} is a known spreading code. This generates SCPU code-gated DMP (CG-DMP) algorithms. [0106] Known or postulated restricted isometry properties (RIP) possessed by s(n), such that it occupies a sparse subset of a basis U.sub.s that is known (oracular basis), or that satisfies some sparsity property (general RIP). This generates adaptive decompression algorithms in compressed sensing applications. [0107] Conjugate self-coherence restoral (C-SCORE) algorithms, in which s(n) is known to have substantive conjugate self-coherence at some known or estimable frequency offset ω, such that

[00027] $\begin{matrix} \frac{.Math. {.Math.}_{n_{sym} = 1}^{N} .Math. .Math. s^{2} (nN + n_{sym}) .Math. e^{- jω .Math. .Math. n_{sym}} .Math.}{{.Math.}_{n_{sym} = 1}^{N} .Math. .Math. {.Math. s (nN - n_{sym}) .Math.}^{2}} \approx 1 & (Eq .Math. .Math. 93) \end{matrix}$ In this case, the enhanced weight update algorithm is given by

[00028] $\begin{matrix} \tilde{w} = \arg .Math. \max_{w \in ℂ^{M_{1} + 1}} .Math. \tilde{ρ} (w | ω; n), & (Eq .Math. .Math. 94) \\ \tilde{ρ} (w | ω; n) = \frac{.Math. w^{H} ({\tilde{X}}^{H} (n) .Math. Δ (ω) .Math. {\tilde{X}}^{*} (n)) .Math. w^{*} .Math.}{w^{H} ({\tilde{X}}^{H} (n) .Math. \tilde{X} .Math. (n)) .Math. w}, .Math. Δ (ω) = diag .Math. {e^{jω .Math. .Math. n_{sym}}}_{n_{sym} = 1}^{N} & (Eq .Math. .Math. 95) \end{matrix}$ [0108] for a postulated twice-carrier offset ω. The enhanced combiner weights {tilde over (w)}.sub.max that maximize (Eq95), and the maximal value of (Eq89), {tilde over (ρ)}.sub.max(ω;n), are equal to the dominant solution {{tilde over (ρ)}.sub.1(ω),{tilde over (w)}.sub.1(ω)} of the C-SCORE pseudo-eigenequation,

{tilde over (ρ)}.sub.m(ω)({tilde over (X)}.sup.H(n){tilde over (X)}((n)){tilde over (w)}.sub.m(ω)=({tilde over (X)}.sup.H(n)Δ(ω){tilde over (X)}*(n)){tilde over (w)}.sub.m*(ω), {tilde over (ρ)}.sub.m≧{tilde over (ρ)}.sub.m+1. (Eq96) The SC-PU C-SCORE algorithm is expected to have application to BPSK, MSK, and GMSK signals, such as 1 Mbps (BPSK) 802.11 DSSS signal. The algorithm also extends to both carrier-tracking algorithms where an FFT-based search algorithm. In this case, the line spectrum used to detect the SOI's will either be the dominant pseudoeigenmode {tilde over (ρ)}.sub.max(ω;n).

[0109] Extensions of all of these algorithms to fully-coupled and uncoupled multiport SCPU methods is straightforward.

[0110] It should also be recognized that, while all of the techniques described here are defined over the “complex field,” such that w∈ custom-character .sup.M, they are equally applicable combiners and optimization metrics defined over other fields, including the real field, e.g., w∈.sup.M, and Galois fields usable in integer field codes. In each case, the subspace constraint

M.sub.0.sup.T(n)w′∝M.sub.0.sup.T(n)w

=M.sub.0.sup.T(n)wg.sub.0, g.sub.0∈ custom-character , (Eq97)

where custom-character is the field in which each element of w is defined, results in a valid SCPU method. The method is also applicable to linear-conjugate-linear (LCL) methods

[00029] $\begin{matrix} {\overline{M}}_{0}^{T} (n) .Math. {\overline{w}}^{'} \propto {\overline{M}}_{0}^{T} (n) .Math. \overline{w}, {\begin{matrix} \overline{w} = \frac{1}{\sqrt{2}} .Math. (\begin{matrix} w \\ w^{*} \end{matrix}) \\ M_{} (n) = [M_{} (n) .Math. .Math. M_{} (n)] \end{matrix} .Math. = {\overline{M}}_{0}^{T} (n) .Math. \overline{w} .Math. {\overline{g}}_{0}, .Math. {\overline{g}}_{0} = \frac{1}{\sqrt{2}} .Math. (\begin{matrix} g_{0} \\ g_{0}^{*} \end{matrix}), & (Eq .Math. .Math. 98) \end{matrix}$ [0111] which allows the SCPU method to be applied to optimization functions that are more complicated functions of complex variables. Moreover the techniques are applicable to processors that implement nonlinear functions on the data path as well as the adapt path, if the original optimization constraint is a linear function of w. In a preferred embodiment the step of performing a dimensionality reduction comprising a linear transformation of the processor parameters being adapted from M-dimensions to (M.sub.1+L)-dimensions in each adaptation event comprises applying a subspace constraint described in the form:

M.sub.0.sup.T(n)w′∝M.sub.0.sup.T(n)w (Eq. 99)

=M.sub.0.sup.T(n)wg.sub.0. (Eq. 100)

[0112] While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail several specific embodiments with the understanding that the present disclosure is to be considered as an exemplification of the principles of the invention and is not intended to limit the invention to the embodiments illustrated.

[0113] Some of the above-described functions may be composed of instructions, or depend upon and use data, that are stored on storage media (e.g., computer-readable medium). The instructions and/or data may be retrieved and executed by the processor. Some examples of storage media are memory devices, tapes, disks, and the like. The instructions are operational when executed by the processor to direct the processor to operate in accord with the invention; and the data is used when it forms part of any instruction or result therefrom.

[0114] The terms “computer-readable storage medium” and “computer-readable storage media” as used herein refer to any medium or media that participate in providing instructions to a CPU for execution. Such media can take many forms, including, but not limited to, non-volatile (also known as ‘static’ or ‘long-term’) media, volatile media and transmission media. Non-volatile media include, for example, one or more optical or magnetic disks, such as a fixed disk, or a hard drive. Volatile media include dynamic memory, such as system RAM or transmission or bus ‘buffers’. Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, a hard disk, magnetic tape, any other magnetic medium, a CD-ROM disk, digital video disk (DVD), any other optical medium, any other physical medium with patterns of marks or holes.

[0115] “Memory”, as used herein when referencing to computers, is the functional hardware that for the period of use retains a specific structure which can be and is used by the computer to represent the coding, whether data or instruction, which the computer uses to perform its function. Memory thus can be volatile or static, and be any of a RAM, a PROM, an EPROM, an EEPROM, a FLASHEPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read data, instructions, or both.

[0116] “I/O”, or ‘input/output’, is any means whereby the computer can exchange information with the world external to the computer. This can include a wired, wireless, acoustic, infrared, or other communications link (including specifically voice or data telephony); a keyboard, tablet, camera, video input, audio input, pen, or other sensor; and a display (2D or 3D, plasma, LED, CRT, tactile, or audio). That which allows another device, or a human, to interact with and exchange data with, or control and command, a computer, is an I/O device, without which any computer (or human) is essentially in a solipsitic state.

[0117] The above description of the invention is illustrative and not restrictive. Many variations of the invention may become apparent to those of skill in the art upon review of this disclosure. The scope of the invention should, therefore, be determined not with reference to the above description, but instead should be determined with reference to the appended claims along with their full scope of equivalents.

[0118] While the present invention has been described in connection with at least one preferred embodiment, these descriptions are not intended to limit the scope of the invention to the particular forms (whether elements of any device or architecture, or steps of any method) set forth herein. It will be further understood that the elements, or steps in methods, of the invention are not necessarily limited to the discrete elements or steps, or the precise connectivity of the elements or order of the steps described, particularly where elements or steps which are part of the prior art are not referenced (and are not claimed). To the contrary, the present descriptions are intended to cover such alternatives, modifications, and equivalents as may be included within the spirit and scope of the invention as defined by the appended claims and otherwise appreciated by one of ordinary skill in the art.

Subspace-constrained partial update method for high-dimensional adaptive processing systems

Inventors

Cpc classification

Classification Explorer

H03H2021/0072

ELECTRICITY

Classification Explorer

G06F17/16

PHYSICS

Classification Explorer

H03H21/0012

ELECTRICITY

Classification Explorer

G06F17/14

PHYSICS

Classification Explorer

H03H21/0043

ELECTRICITY

International classification

Classification Explorer

G06F17/14

PHYSICS

Classification Explorer

G06F17/16

PHYSICS

Abstract

Claims

Description