Main Content

# fixed.complexQlessQRMatrixSolveFixedpointTypes

Determine fixed-point types for matrix solution of complex-valued A'AX=B using QR decomposition

## Syntax

``T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,precisionBits)``
``T = fixed.complexQlessQRMatrixSolveFixedpointTypes(___,noiseStandardDeviation,p_s)``
``T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,precisionBits,noiseStandardDeviation,p_s,regularizationParameter)``

## Description

example

````T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,precisionBits)` computes fixed-point types for the matrix solution of complex-valued A'AX=B using QR decomposition. T is returned as a struct with fields that specify fixed-point types for A and B that guarantee no overflow will occur in the QR algorithm transforming A in-place into upper-triangular R, where QR=A is the QR decomposition of X, and X such that there is a low probability of overflow.```

example

````T = fixed.complexQlessQRMatrixSolveFixedpointTypes(___,noiseStandardDeviation,p_s)` specifies the standard deviation of the additive random noise in A and the probability that the estimate of the lower bound for the smallest singular value of A is larger than the actual smallest singular value of the matrix.```

example

````T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,precisionBits,noiseStandardDeviation,p_s,regularizationParameter)` computes fixed-point types for the matrix solution of complex-valued ${\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{\text{'}}\cdot \left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]X=\left({\lambda }^{2}{I}_{n}+A\text{'}A\right)X=B$ where λ is the `regularizationParameter`, A is an m-by-n matrix, and In = `eye(n)`.`noiseStandardDeviation`, `p_s`, and `regularizationParameter` are optional parameters. If not supplied or empty, then their default values are used.```

## Examples

collapse all

This example shows how to use the `fixed.complexQlessQRMatrixSolveFixedpointTypes` function to analytically determine fixed-point types for the solution of the complex least-squares matrix equation ${A}^{\prime }AX=B$, where $A$ is an $m$-by-$n$ matrix with $m\ge n$, $B$ is $n$-by-$p$, and $X$ is $n$-by-$p$.

Fixed-point types for the solution of the matrix equation ${A}^{\prime }AX=B$ are well-bounded if the number of rows, $m$, of $A$ are much greater than the number of columns, $n$ (i.e. $m\gg n$), and $A$ is full rank. If $A$ is not inherently full rank, then it can be made so by adding random noise. Random noise naturally occurs in physical systems, such as thermal noise in radar or communications systems. If $m=n$, then the dynamic range of the system can be unbounded, for example in the scalar equation $x=a/b$ and $a,b\in \left[-1,1\right]$, then $x$ can be arbitrarily large if $b$ is close to $0$.

Define System Parameters

Define the matrix attributes and system parameters for this example.

`m` is the number of rows in matrix `A`. In a problem such as beamforming or direction finding, `m` corresponds to the number of samples that are integrated over.

`m = 300;`

`n` is the number of columns in matrix `A` and rows in matrices B and `X`. In a least-squares problem, `m` is greater than `n`, and usually `m` is much larger than `n`. In a problem such as beamforming or direction finding, `n` corresponds to the number of sensors.

`n = 10;`

`p` is the number of columns in matrices `B` and `X`. It corresponds to simultaneously solving a system with `p` right-hand sides.

`p = 1;`

In this example, set the rank of matrix `A` to be less than the number of columns. In a problem such as beamforming or direction finding, $\text{rank}\left(A\right)$ corresponds to the number of signals impinging on the sensor array.

`rankA = 3;`

`precisionBits` defines the number of bits of precision required for the matrix solve. Set this value according to system requirements.

`precisionBits = 24;`

In this example, complex-valued matrices `A` and `B` are constructed such that the magnitude of the real and imaginary parts of their elements is less than or equal to one, so the maximum possible absolute value of any element is $|1+1i|=\sqrt{2}$. Your own system requirements will define what those values are. If you don't know what they are, and `A` and `B` are fixed-point inputs to the system, then you can use the `upperbound` function to determine the upper bounds of the fixed-point types of `A` and `B`.

`max_abs_A` is an upper bound on the maximum magnitude element of A.

`max_abs_A = sqrt(2);`

`max_abs_B` is an upper bound on the maximum magnitude element of B.

`max_abs_B = sqrt(2);`

Thermal noise standard deviation is the square root of thermal noise power, which is a system parameter. A well-designed system has the quantization level lower than the thermal noise. Here, set `thermalNoiseStandardDeviation` to the equivalent of $-50$dB noise power.

`thermalNoiseStandardDeviation = sqrt(10^(-50/10))`
```thermalNoiseStandardDeviation = 0.0032 ```

The quantization noise standard deviation is a function of the required number of bits of precision. Use `fixed.complexQuantizationNoiseStandardDeviation` to compute this. See that it is less than `thermalNoiseStandardDeviation`.

`quantizationNoiseStandardDeviation = fixed.complexQuantizationNoiseStandardDeviation(precisionBits)`
```quantizationNoiseStandardDeviation = 2.4333e-08 ```

Compute Fixed-Point Types

In this example, assume that the designed system matrix $A$ does not have full rank (there are fewer signals of interest than number of columns of matrix $A$), and the measured system matrix $A$ has additive thermal noise that is larger than the quantization noise. The additive noise makes the measured matrix $A$ have full rank.

Set .

`noiseStandardDeviation = thermalNoiseStandardDeviation;`

Use the `fixed.complexQlessQRMatrixSolveFixedpointTypes` function to compute fixed-point types.

```T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,... precisionBits,noiseStandardDeviation)```
```T = struct with fields: A: [0x0 embedded.fi] B: [0x0 embedded.fi] X: [0x0 embedded.fi] ```

`T.A` is the type computed for transforming $\mathit{A}$ to $\mathit{R}={\mathit{Q}}^{\prime }\mathit{A}$ in-place so that it does not overflow.

`T.A`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 32 FractionLength: 24 ```

`T.B` is the type computed for B so that it does not overflow.

`T.B`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 27 FractionLength: 24 ```

`T.X` is the type computed for the solution $X=\left({A}^{\prime }A\right)\B$ so that there is a low probability that it overflows.

`T.X`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 40 FractionLength: 24 ```

Use the Specified Types to Solve the Matrix Equation A'AX=B

Create random matrices `A` and `B` such that `rankA=rank(A)`. Add random measurement noise to `A` which will make it become full rank.

```rng('default'); [A,B] = fixed.example.complexRandomQlessQRMatrices(m,n,p,rankA); A = A + fixed.example.complexNormalRandomArray(0,noiseStandardDeviation,m,n);```

Cast the inputs to the types determined by `fixed.complexQlessQRMatrixSolveFixedpointTypes`. Quantizing to fixed-point is equivalent to adding random noise.

```A = cast(A,'like',T.A); B = cast(B,'like',T.B);```

Accelerate the `fixed.qlessQRMatrixSolve` function by using `fiaccel` to generate a MATLAB executable (MEX) function.

`fiaccel fixed.qlessQRMatrixSolve -args {A,B,T.X} -o qlessQRMatrixSolve_mex`

Specify output type `T.X` and compute fixed-point $X=\left({A}^{\prime }A\right)\B$ using the QR method.

`X = qlessQRMatrixSolve_mex(A,B,T.X);`

Compute the relative error to verify the accuracy of the output.

`relative_error = norm(double(A'*A*X - B))/norm(double(B))`
```relative_error = 0.1052 ```

Suppress `mlint` warnings in this file.

```%#ok<*NASGU> %#ok<*ASGLU>```

This example shows how to use the `fixed.complexQlessQRMatrixSolveFixedpointTypes` function to analytically determine fixed-point types for the solution of the complex least-squares matrix equation

`${\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{H}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]X=\left({\lambda }^{2}{I}_{n}+{A}^{H}A\right)X=B$`

where $A$ is an $m$-by-$n$ matrix with $m\ge n$, $B$ is $n$-by-$p$, $X$ is $n$-by-$p$, ${I}_{n}=\text{eye}\left(n\right)$, and $\lambda$ is a regularization parameter.

Define System Parameters

Define the matrix attributes and system parameters for this example.

`m` is the number of rows in matrix `A`. In a problem such as beamforming or direction finding, `m` corresponds to the number of samples that are integrated over.

`m = 300;`

`n` is the number of columns in matrix `A` and rows in matrices B and `X`. In a least-squares problem, `m` is greater than `n`, and usually `m` is much larger than `n`. In a problem such as beamforming or direction finding, `n` corresponds to the number of sensors.

`n = 10;`

`p` is the number of columns in matrices `B` and `X`. It corresponds to simultaneously solving a system with `p` right-hand sides.

`p = 1;`

In this example, set the rank of matrix `A` to be less than the number of columns. In a problem such as beamforming or direction finding, $\text{rank}\left(A\right)$ corresponds to the number of signals impinging on the sensor array.

`rankA = 3;`

`precisionBits` defines the number of bits of precision required for the matrix solve. Set this value according to system requirements.

`precisionBits = 32;`

Small, positive values of the regularization parameter can improve the conditioning of the problem and reduce the variance of the estimates. While biased, the reduced variance of the estimate often results in a smaller mean squared error when compared to least-squares estimates.

`regularizationParameter = 0.01;`

In this example, complex-valued matrices `A` and `B` are constructed such that the magnitude of the real and imaginary parts of their elements is less than or equal to one, so the maximum possible absolute value of any element is $|1+1i|=\sqrt{2}$. Your own system requirements will define what those values are. If you don't know what they are, and `A` and `B` are fixed-point inputs to the system, then you can use the `upperbound` function to determine the upper bounds of the fixed-point types of `A` and `B`.

`max_abs_A` is an upper bound on the maximum magnitude element of A.

`max_abs_A = sqrt(2);`

`max_abs_B` is an upper bound on the maximum magnitude element of B.

`max_abs_B = sqrt(2);`

Thermal noise standard deviation is the square root of thermal noise power, which is a system parameter. A well-designed system has the quantization level lower than the thermal noise. Here, set `thermalNoiseStandardDeviation` to the equivalent of $-50$dB noise power.

`thermalNoiseStandardDeviation = sqrt(10^(-50/10))`
```thermalNoiseStandardDeviation = 0.0032 ```

The quantization noise standard deviation is a function of the required number of bits of precision. Use `fixed.complexQuantizationNoiseStandardDeviation` to compute this. See that it is less than `thermalNoiseStandardDeviation`.

`quantizationNoiseStandardDeviation = fixed.complexQuantizationNoiseStandardDeviation(precisionBits)`
```quantizationNoiseStandardDeviation = 9.5053e-11 ```

Compute Fixed-Point Types

In this example, assume that the designed system matrix $A$ does not have full rank (there are fewer signals of interest than number of columns of matrix $A$), and the measured system matrix $A$ has additive thermal noise that is larger than the quantization noise. The additive noise makes the measured matrix $A$ have full rank.

Set .

`noiseStandardDeviation = thermalNoiseStandardDeviation;`

Use the `fixed.complexQlessQRMatrixSolveFixedpointTypes` function to compute fixed-point types.

```T = fixed.complexQlessQRMatrixSolveFixedpointTypes(m,n,max_abs_A,max_abs_B,... precisionBits,noiseStandardDeviation,[],regularizationParameter)```
```T = struct with fields: A: [0x0 embedded.fi] B: [0x0 embedded.fi] X: [0x0 embedded.fi] ```

`T.A` is the type computed for transforming $\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]$ to $R={Q}^{H}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]$ in-place so that it does not overflow.

`T.A`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 40 FractionLength: 32 ```

`T.B` is the type computed for B so that it does not overflow.

`T.B`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 35 FractionLength: 32 ```

`T.X` is the type computed for the solution $X=\left({\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{H}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]\right)\B$ so that there is a low probability that it overflows.

`T.X`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 48 FractionLength: 32 ```

Use the Specified Types to Solve the Matrix Equation

Create random matrices `A` and `B` such that `rankA=rank(A)`. Add random measurement noise to `A` which will make it become full rank.

```rng('default'); [A,B] = fixed.example.complexRandomQlessQRMatrices(m,n,p,rankA); A = A + fixed.example.complexNormalRandomArray(0,noiseStandardDeviation,m,n);```

Cast the inputs to the types determined by `fixed.complexQlessQRMatrixSolveFixedpointTypes`. Quantizing to fixed-point is equivalent to adding random noise.

```A = cast(A,'like',T.A); B = cast(B,'like',T.B);```

Accelerate the `fixed.qlessQRMatrixSolve` function by using `fiaccel` to generate a MATLAB executable (MEX) function.

`fiaccel +fixed/qlessQRMatrixSolve -args {A,B,T.X,[],regularizationParameter} -o qlessQRMatrixSolve_mex`

Specify output type `T.X` and compute fixed-point $X=\left({\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{H}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]\right)\B$ using the QR method.

`X = qlessQRMatrixSolve_mex(A,B,T.X,[],regularizationParameter);`

Verify the Accuracy of the Output

Verify that the relative error between the fixed-point output and builtin MATLAB in double-precision floating-point is small.

`${X}_{\text{double}}=\left({\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{H}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]\right)\B$`

```A_lambda = double([regularizationParameter*eye(n);A]); X_double = (A_lambda'*A_lambda)\double(B); relativeError = norm(X_double - double(X))/norm(X_double)```
```relativeError = 1.0591e-05 ```

Suppress `mlint` warnings in this file.

```%#ok<*NASGU> %#ok<*ASGLU>```

## Input Arguments

collapse all

Number of rows in A and B, specified as a positive integer-valued scalar.

Data Types: `double`

Number of columns in A, specified as a positive integer-valued scalar.

Data Types: `double`

Maximum of the absolute value of A, specified as a scalar.

Example: `max(abs(A(:)))`

Data Types: `double`

Maximum of the absolute value of B, specified as a scalar.

Example: `max(abs(B(:)))`

Data Types: `double`

Required number of bits of precision of the input and output, specified as a positive integer-valued scalar.

Data Types: `double`

Standard deviation of additive random noise in A, specified as a scalar.

If `noiseStandardDeviation` is not specified, then the default is the standard deviation of the complex-valued quantization noise ${\sigma }_{q}=\left({2}^{-\mathrm{precisionBits}}\right)/\left(\sqrt{6}\right)$, which is calculated by `fixed.complexQuantizationNoiseStandardDeviation`.

Data Types: `double`

Probability that estimate of lower bound s is larger than actual smallest singular value of matrix, specified as a scalar. Use `fixed.complexSingularValueLowerBound` to estimate the smallest singular value, s, of A. If `p_s` is not specified, the default value is ${p}_{s}=\left(1/2\right)\cdot \left(1+\text{erf}\left(-5/\sqrt{2}\right)\right)\approx 3\cdot {10}^{-7}$ which is 5 standard deviations below the mean, so the probability that the estimated bound for the smallest singular value is less than the actual smallest singular value is 1-ps ≈ 0.9999997.

Data Types: `double`

Regularization parameter, specified as a nonnegative scalar. Small, positive values of the regularization parameter can improve the conditioning of the problem and reduce the variance of the estimates. While biased, the reduced variance of the estimate often results in a smaller mean squared error when compared to least-squares estimates.

`regularizationParameter` is the Tikhonov regularization parameter of the matrix problem

`${\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]}^{\text{'}}\cdot \left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]X=\left({\lambda }^{2}{I}_{n}+A\text{'}A\right)X=B$`

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `int64` | `uint8` | `uint16` | `uint32` | `uint64` | `fi`

## Output Arguments

collapse all

Fixed-point types for A, B, and X, returned as a struct. The struct `T` has fields `T.A`, `T.B`, and `T.X`. These fields contain `fi` objects that specify fixed-point types for

• A and B that guarantee no overflow will occur in the QR algorithm.

The QR algorithm transforms A in-place into upper-triangular R where QR=A is the QR decomposition of A.

• X such that there is a low probability of overflow.

## Tips

Use `fixed.complexQlessQRMatrixSolveFixedpointTypes` to compute fixed-point types for the inputs of these functions and blocks.

## Algorithms

The fixed-point type for A is computed using `fixed.qlessqrFixedpointTypes`. The required number of integer bits to prevent overflow is derived from the following bound on the growth of R [1]. The required number of integer bits is added to the number of bits of precision, `precisionBits`, of the input, plus one for the sign bit, plus one bit for intermediate CORDIC gain of approximately 1.6468 [2].

The elements of R are bounded in magnitude by

`$\mathrm{max}\left(|R\left(:\right)|\right)\le \sqrt{m}\mathrm{max}\left(|A\left(:\right)|\right).$`

Matrix B is not transformed, so it does not need any additional growth bits.

The elements of X=R\(R'\B) are bounded in magnitude by

`$\mathrm{max}\left(|X\left(:\right)|\right)\le \frac{n\cdot \mathrm{max}\left(|B\left(:\right)|\right)}{\mathrm{min}{\left(\text{svd}\left(A\right)\right)}^{2}}.$`

Computing the singular value decomposition to derive the above bound on X is more computationally intensive than the entire matrix solve, so the `fixed.complexSingularValueLowerBound` function is used to estimate a bound on `min(svd(A))`.

## References

[2] Voler, Jack E. "The CORDIC Trigonometric Computing Technique." IRE Transactions on Electronic Computers EC-8 (1959): 330-334.

## Version History

Introduced in R2021b