# fixed.complexQRMatrixSolveFixedpointTypes

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

## Syntax

## Description

computes fixed-point types for the matrix solution of complex-valued
`T`

= fixed.complexQRMatrixSolveFixedpointTypes(`m`

,`n`

,`max_abs_A`

,`max_abs_B`

,`precisionBits`

)*A**X*=*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, and *X* such that there is a low probability of
overflow.

The QR algorithm transforms *A* in-place into upper-triangular
*R* and transforms *B* in-place into *C*=*Q*'*B*, where *Q**R*=*A* is the QR decomposition of *A*.

specifies the standard deviation of the additive random noise in `T`

= fixed.complexQRMatrixSolveFixedpointTypes(___,`noiseStandardDeviation`

)*A*.
`noiseStandardDeviation`

is an optional parameter. If not supplied or
empty, then the default value is used.

specifies the probability that the estimate of the lower bound for the smallest singular
value of `T`

= fixed.complexQRMatrixSolveFixedpointTypes(___,`p_s`

)*A* is larger than the actual smallest singular value of the
matrix. `p_s`

is an optional parameter. If not supplied or empty, then
the default value is used.

computes fixed-point types for the matrix solution of complex-valued $$\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]X=\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$ where `T`

= fixed.complexQRMatrixSolveFixedpointTypes(___,`regularizationParameter`

)*λ* is the
`regularizationParameter`

, *A* is an
*m*-by-*n* matrix, *p* is the number of
columns in *B*, *I _{n}* =

`eye(`*n*)

, and
*0*=

_{n,p}`zeros(`*n*,*p*)

.
`regularizationParameter`

is an optional parameter. If not supplied or
empty, then the default value is used.

specifies the maximum word length of the fixed-point types.
`T`

= fixed.complexQRMatrixSolveFixedpointTypes(___,`maxWordLength`

)`maxWordLength`

is an optional parameter. If not supplied or empty,
then the default value is used.

## Examples

### Algorithms to Determine Fixed-Point Types for Complex Q-less QR Matrix Solve A'AX=B

This example shows the algorithms that the `fixed.complexQlessQRMatrixSolveFixedpointTypes`

function uses to analytically determine fixed-point types for the solution of the complex 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$$.

**Overview**

You can solve the fixed-point matrix equation $${A}^{\prime}AX=B$$ using QR decomposition. Using a sequence of orthogonal transformations, QR decomposition transforms matrix $$A$$ in-place to upper triangular $$R$$, where $$QR=A$$ is the economy-size QR decomposition. This reduces the equation to an upper-triangular system of equations $${R}^{\prime}RX=B$$. To solve for $$X$$, compute $$X=R\backslash ({R}^{\prime}\backslash B)$$ through forward- and backward-substitution of $$R$$ into $$B$$.

You can determine appropriate fixed-point types for the matrix equation $${A}^{\prime}AX=B$$ by selecting the fraction length based on the number of bits of precision defined by your requirements. The `fixed.complexQlessQRMatrixSolveFixedpointTypes`

function analytically computes the following upper bounds on $$R$$, and $$X$$ to determine the number of integer bits required to avoid overflow [1,2,3].

The upper bound for the magnitude of the elements of $$R={Q}^{\prime}A$$ is

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

The upper bound for the magnitude of the elements of $$X=({A}^{\prime}A)\backslash B$$ is

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

Since computing $$\text{svd}(A)$$ is more computationally expensive than solving the system of equations, the `fixed.complexQlessQRMatrixSolveFixedpointTypes`

function estimates a lower bound of $$\mathrm{min}(\text{svd}(A))$$.

Fixed-point types for the solution of the matrix equation $$({A}^{\prime}A)X=B$$ are generally 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}^{2}/b$$ and $$a,b\in [-1,1]$$, then $$x$$ can be arbitrarily large if $$b$$ is close to $$0$$.

**Proofs of the Bounds**

**Properties and Definitions of Vector and Matrix Norms**

The proofs of the bounds use the following properties and definitions of matrix and vector norms, where $$Q$$ is an orthogonal matrix, and $$v$$ is a vector of length $$m$$ [6].

$$\begin{array}{lcl}||Av|{|}_{2}& \le & ||A|{|}_{2}||v|{|}_{2}\\ ||Q|{|}_{2}& =& 1\\ ||v|{|}_{\infty}& =& \mathrm{max}(|v(:)|)\\ ||v|{|}_{\infty}& \le & ||v|{|}_{2}\phantom{\rule{0.2777777777777778em}{0ex}}\le \phantom{\rule{0.2777777777777778em}{0ex}}\sqrt{m}||v|{|}_{\infty}\end{array}$$

If $$A$$ is an $$m$$-by-$$n$$ matrix and $$QR=A$$ is the economy-size QR decomposition of $$A$$, where $$Q$$ is orthogonal and $$m$$-by-$$n$$ and $$R$$ is upper-triangular and $$n$$-by-$$n$$, then the singular values of $$R$$ are equal to the singular values of $$A$$. If $$A$$ is nonsingular, then

$$||{R}^{-1}|{|}_{2}=||({R}^{\prime}{)}^{-1}|{|}_{2}=\frac{1}{\mathrm{min}(\text{svd}(R))}=\frac{1}{\mathrm{min}(\text{svd}(A))}$$

**Upper Bound for R = Q'A**

The upper bound for the magnitude of the elements of $$R$$ is

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

**Proof of Upper Bound for R = Q'A**

The $$j$$th column of $$R$$ is equal to $$R(:,j)={Q}^{\prime}A(:,j)$$, so

$$\begin{array}{rcl}\mathrm{max}(|R(:,j)|)& =& ||R(:,j)|{|}_{\infty}\\ & \le & ||R(:,j)|{|}_{2}\\ & =& ||{Q}^{\prime}A(:,j)|{|}_{2}\\ & \le & ||{Q}^{\prime}|{|}_{2}||A(:,j)|{|}_{2}\\ & =& ||A(:,j)|{|}_{2}\\ & \le & \sqrt{m}||A(:,j)|{|}_{\infty}\\ & =& \sqrt{m}\mathrm{max}(|A(:,j)|)\\ & \le & \sqrt{m}\mathrm{max}(|A(:)|).\end{array}$$

Since $$\mathrm{max}(|R(:,j)|)\le \sqrt{m}\mathrm{max}(|A(:)|)$$ for all $$1\le j$$, then

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

**Upper Bound for X = (A'A)\B**

The upper bound for the magnitude of the elements of $$X=({A}^{\prime}A)\backslash B$$ is

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

**Proof of Upper Bound for X = (A'A)\B**

If $$A$$ is not full rank, then $$\mathrm{min}(\text{svd}(A))=0$$, and if $$B$$ is not equal to zero, then $$\sqrt{n}\mathrm{max}(|B(:)|)/\mathrm{min}(\text{svd}(A){)}^{2}=\infty $$and so the inequality is true.

If $${A}^{\prime}Ax=b$$ and $$QR=A$$ is the economy-size QR decomposition of $$A$$, then $${A}^{\prime}Ax={R}^{\prime}{Q}^{\prime}QRx={R}^{\prime}Rx=b$$. If $$A$$ is full rank then $$x={R}^{-1}\cdot (({R}^{\prime}{)}^{-1}b)$$. Let $$x=X(:,j)$$ be the $$j$$th column of $$X$$, and $$b=B(:,j)$$ be the $$j$$th column of $$B$$. Then

$$\begin{array}{rcl}\mathrm{max}(|x(:)|)& =& ||x|{|}_{\infty}\\ & \le & ||x|{|}_{2}\\ & =& ||{R}^{-1}\cdot (({R}^{\prime}{)}^{-1}b)|{|}_{2}\\ & \le & ||{R}^{-1}|{|}_{2}||({R}^{\prime}{)}^{-1}|{|}_{2}||b|{|}_{2}\\ & =& (1/\mathrm{min}(\text{svd}(A){)}^{2})\cdot ||b|{|}_{2}\\ & =& ||b|{|}_{2}/\mathrm{min}(\text{svd}(A){)}^{2}\\ & \le & \sqrt{n}||b|{|}_{\infty}/\mathrm{min}(\text{svd}(A){)}^{2}\\ & =& \sqrt{n}\mathrm{max}(|b(:)|)/\mathrm{min}(\text{svd}(A){)}^{2}.\end{array}$$

Since $$\mathrm{max}(|x(:)|)\le \sqrt{n}\mathrm{max}(|b(:)|)/\mathrm{min}(\text{svd}(A){)}^{2}$$ for all rows and columns of $$B$$ and $$X$$, then

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

**Lower Bound for min(svd(A))**

You can estimate a lower bound $$s$$ of $$\mathrm{min}(\text{svd}(A))$$for complex-valued $$A$$ using the following formula,

$$s=\frac{{\sigma}_{N}}{\sqrt{2}}\sqrt{{\gamma}^{-1}(\frac{{p}_{s}\phantom{\rule{0.16666666666666666em}{0ex}}{\Gamma (m-n+2)}^{2}\phantom{\rule{0.16666666666666666em}{0ex}}\Gamma \left(n\right)}{\Gamma (m+1)\phantom{\rule{0.16666666666666666em}{0ex}}\Gamma (m-n+1)(m-n+1)},\phantom{\rule{0.2777777777777778em}{0ex}}m-n+1)}$$

where $${\sigma}_{N}$$ is the standard deviation of random noise added to the elements of $$A$$, $$1-{p}_{s}$$ is the probability that $$s\le \mathrm{min}(\text{svd}(A))$$, $$\Gamma $$ is the `gamma`

function, and $${\gamma}^{-1}$$is the inverse incomplete gamma function `gammaincinv`

.

The proof is found in [1]. It is derived by integrating the formula in Lemma 3.4 from [3] and rearranging terms.

Since $$s\le \mathrm{min}(\text{svd}(A))$$ with probability $$1-{p}_{s}$$, then you can bound the magnitude of the elements of $$X$$ without computing $$\text{svd}(A)$$,

$$\mathrm{max}(|X(:)|)\le \frac{\sqrt{n}\mathrm{max}(|B(:)|)}{\mathrm{min}(\text{svd}(A){)}^{2}}\le \frac{\sqrt{n}\mathrm{max}(|B(:)|)}{{s}^{2}}$$ with probability $$1-{p}_{s}$$.

You can compute $$s$$ using the `fixed.complexSingularValueLowerBound`

function which uses a default probability of 5 standard deviations below the mean, $${p}_{s}=(1+\text{erf}(-5/\sqrt{2}))/2\approx 2.8665\cdot 1{0}^{-7}$$, so the probability that the estimated bound for the smallest singular value $$s$$ is less than the actual smallest singular value of $$A$$ is $$1-{p}_{s}\approx 0.9999997$$.

**Example**

This example runs a simulation with many random matrices and compares the analytical bounds with the actual singular values of $$A$$ and the actual largest elements of $$R={Q}^{\prime}A$$, and $$X=({A}^{\prime}A)\backslash B$$.

**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}(A)$$ 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 standard deviation of the noise from quantizing the real and imaginary parts of a complex signal is $${2}^{-\text{precisionBits}}/\sqrt{6}$$ [4,5]. 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 $${\sigma}_{\text{noise}}={\sigma}_{\text{thermal}\text{}\text{noise}}$$.

noiseStandardDeviation = thermalNoiseStandardDeviation;

Use `fixed.complexQlessQRMatrixSolveFixedpointTypes`

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}$ 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=({A}^{\prime}A)\backslash 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

**Upper Bound for R**

The upper bound for $$R$$ is computed using the formula $$\mathrm{max}(|R(:)|)\le \sqrt{m}\mathrm{max}(|A(:)|)$$, where $$m$$ is the number of rows of matrix $$A$$. This upper bound is used to select a fixed-point type with the required number of bits of precision to avoid an overflow in the upper bound.

upperBoundR = sqrt(m)*max_abs_A

upperBoundR = 24.4949

**Lower Bound for min(svd(A)) for Complex A**

A lower bound for $$\mathrm{min}(\text{svd}(A))$$ is estimated by the `fixed.complexSingularValueLowerBound`

function using a probability that the estimate $$s$$ is not greater than the actual smallest singular value. The default probability is 5 standard deviations below the mean. You can change this probability by specifying it as the last input parameter to the `fixed.complexSingularValueLowerBound`

function.

estimatedSingularValueLowerBound = fixed.complexSingularValueLowerBound(m,n,noiseStandardDeviation)

estimatedSingularValueLowerBound = 0.0389

**Simulate and Compare to the Computed Bounds**

The bounds are within an order of magnitude of the simulated results. This is sufficient because the number of bits translates to a logarithmic scale relative to the range of values. Being within a factor of 10 is between 3 and 4 bits. This is a good starting point for specifying a fixed-point type. If you run the simulation for more samples, then it is more likely that the simulated results will be closer to the bound. This example uses a limited number of simulations so it doesn't take too long to run. For real-world system design, you should run additional simulations.

Define the number of samples, `numSamples`

, over which to run the simulation.

numSamples = 1e4;

Run the simulation.

```
[actualMaxR,singularValues,X_values] = runSimulations(m,n,p,rankA,max_abs_A,max_abs_B,numSamples,...
noiseStandardDeviation,T);
```

You can see that the upper bound on $$R$$ compared to the measured simulation results of the maximum value of $$R$$ over all runs is within an order of magnitude.

upperBoundR

upperBoundR = 24.4949

max(actualMaxR)

ans = 9.4990

Finally, see that the estimated lower bound of $$\mathrm{min}(\text{svd}(A))$$ compared to the measured simulation results of $$\mathrm{min}(\text{svd}(A))$$ over all runs is also within an order of magnitude.

estimatedSingularValueLowerBound

estimatedSingularValueLowerBound = 0.0389

`actualSmallestSingularValue = min(singularValues,[],'all')`

actualSmallestSingularValue = 0.0443

Plot the distribution of the singular values over all simulation runs. The distributions of the largest singular values correspond to the signals that determine the rank of the matrix. The distributions of the smallest singular values correspond to the noise. The derivation of the estimated bound of the smallest singular value makes use of the random nature of the noise.

clf fixed.example.plot.singularValueDistribution(m,n,rankA,... noiseStandardDeviation,singularValues,... estimatedSingularValueLowerBound,"complex");

Zoom in to the smallest singular value to see that the estimated bound is close to it.

xlim([estimatedSingularValueLowerBound*0.9, max(singularValues(n,:))]);

Estimate the largest value of the solution, X, and compare it to the largest value of X found during the simulation runs. The estimation is within an order of magnitude of the actual value, which is sufficient for estimating a fixed-point data type, because it is between 3 and 4 bits.

This example uses a limited number of simulation runs. With additional simulation runs, the actual largest value of X will approach the estimated largest value of X.

estimated_largest_X = fixed.complexQlessQRMatrixSolveUpperBoundX(m,n,max_abs_B,noiseStandardDeviation)

estimated_largest_X = 9.3348e+03

`actual_largest_X = max(abs(X_values),[],'all')`

actual_largest_X = 977.7440

Plot the distribution of X values and compare it to the estimated upper bound for X.

clf fixed.example.plot.xValueDistribution(m,n,rankA,noiseStandardDeviation,... X_values,estimated_largest_X,"complex normally distributed random");

**Supporting Functions**

The `runSimulations`

function creates a series of random matrices $$A$$ and $$B$$ of a given size and rank, quantizes them according to the computed types, computes the QR decomposition of $$A$$, and solves the equation $${A}^{\prime}AX=B$$. It returns the maximum values of $$R={Q}^{\prime}A$$, the singular values of $$A$$, and the values of $$X$$ so their distributions can be plotted and compared to the bounds.

function [actualMaxR,singularValues,X_values] = runSimulations(m,n,p,rankA,max_abs_A,max_abs_B,... numSamples,noiseStandardDeviation,T) precisionBits = T.A.FractionLength; A_WordLength = T.A.WordLength; B_WordLength = T.B.WordLength; actualMaxR = zeros(1,numSamples); singularValues = zeros(n,numSamples); X_values = zeros(n,numSamples); for j = 1:numSamples A = (max_abs_A/sqrt(2))*fixed.example.complexRandomLowRankMatrix(m,n,rankA); % Adding random noise makes A non-singular. A = A + fixed.example.complexNormalRandomArray(0,noiseStandardDeviation,m,n); A = quantizenumeric(A,1,A_WordLength,precisionBits); B = fixed.example.complexUniformRandomArray(-max_abs_B,max_abs_B,n,p); B = quantizenumeric(B,1,B_WordLength,precisionBits); [~,R] = qr(A,0); X = R\(R'\B); actualMaxR(j) = max(abs(R(:))); singularValues(:,j) = svd(A); X_values(:,j) = X; end end

**References**

Thomas A. Bryan and Jenna L. Warren. “Systems and Methods for Design Parameter Selection”. Patent pending. U.S. Patent Application No. 16/947,130. 2020.

Perform QR Factorization Using CORDIC. Derivation of the bound on growth when computing QR. MathWorks. 2010. url: https://www.mathworks.com/help/fixedpoint/ug/perform-qr-factorization-using-cordic.html.

Zizhong Chen and Jack J. Dongarra. “Condition Numbers of Gaussian Random Matrices”. In: SIAM J. Matrix Anal. Appl. 27.3 (July 2005), pp. 603–620. issn: 0895-4798. doi: 10.1137/040616413. url: https://dx.doi.org/10.1137/040616413.

Bernard Widrow. “A Study of Rough Amplitude Quantization by Means of Nyquist Sampling Theory”. In: IRE Transactions on Circuit Theory 3.4 (Dec. 1956), pp. 266–276.

Bernard Widrow and István Kollár. Quantization Noise – Roundoff Error in Digital Computation, Signal Processing, Control, and Communications. Cambridge, UK: Cambridge University Press, 2008.

Gene H. Golub and Charles F. Van Loan. Matrix Computations. Second edition. Baltimore: Johns Hopkins University Press, 1989.

Suppress mlint warnings in this file.

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

### Algorithms to Determine Fixed-Point Types for Complex Least-Squares Matrix Solve AX=B

This example shows the algorithms that the `fixed.complexQRMatrixSolveFixedpointTypes`

function uses to analytically determine fixed-point types for the solution of the complex least-squares matrix equation $$AX=B$$, where $$A$$ is an $$m$$-by-$$n$$ matrix with $$m\ge n$$, $$B$$ is $$m$$-by-$$p$$, and $$X$$ is $$n$$-by-$$p$$.

**Overview**

You can solve the fixed-point least-squares matrix equation $$AX=B$$ using QR decomposition. Using a sequence of orthogonal transformations, QR decomposition transforms matrix $$A$$ in-place to upper triangular $$R$$, and transforms matrix $$B$$ in-place to $C={Q}^{\prime}B$, where $$QR=A$$ is the economy-size QR decomposition. This reduces the equation to an upper-triangular system of equations $$RX=C$$. To solve for $\mathit{X}$, compute $$X=R\backslash C$$ through back-substitution of $$R$$ into $$C$$.

You can determine appropriate fixed-point types for the least-squares matrix equation $$AX=B$$ by selecting the fraction length based on the number of bits of precision defined by your requirements. The `fixed.complexQRMatrixSolveFixedpointTypes`

function analytically computes the following upper bounds on $$R={Q}^{\prime}A$$, $$C={Q}^{\prime}B$$, and $$X$$ to determine the number of integer bits required to avoid overflow [1,2,3].

The upper bound for the magnitude of the elements of $$R={Q}^{\prime}A$$ is

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

The upper bound for the magnitude of the elements of $$C={Q}^{\prime}B$$ is

$$\mathrm{max}(|C(:)|)\le \sqrt{m}\mathrm{max}(|B(:)|)$$.

The upper bound for the magnitude of the elements of $$X=A\backslash B$$ is

$$\mathrm{max}(|X(:)|)\le \frac{\sqrt{m}\mathrm{max}(|B(:)|)}{\mathrm{min}(\text{svd}(A))}$$.

Since computing $$\text{svd}(A)$$ is more computationally expensive than solving the system of equations, the `fixed.complexQRMatrixSolveFixedpointTypes`

function estimates a lower bound of $$\mathrm{min}(\text{svd}(A))$$.

Fixed-point types for the solution of the matrix equation $$AX=B$$ are generally 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 [-1,1]$$, then $$x$$ can be arbitrarily large if $$b$$ is close to $$0$$.

**Proofs of the Bounds**

**Properties and Definitions of Vector and Matrix Norms**

The proofs of the bounds use the following properties and definitions of matrix and vector norms, where $$Q$$ is an orthogonal matrix, and $$v$$ is a vector of length $$m$$ [6].

$$\begin{array}{lcl}||Av|{|}_{2}& \le & ||A|{|}_{2}||v|{|}_{2}\\ ||Q|{|}_{2}& =& 1\\ ||v|{|}_{\infty}& =& \mathrm{max}(|v(:)|)\\ ||v|{|}_{\infty}& \le & ||v|{|}_{2}\phantom{\rule{0.2777777777777778em}{0ex}}\le \phantom{\rule{0.2777777777777778em}{0ex}}\sqrt{m}||v|{|}_{\infty}\end{array}$$

If $$A$$ is an $$m$$-by-$$n$$ matrix and $$QR=A$$ is the economy-size QR decomposition of $$A$$, where $$Q$$ is orthogonal and $$m$$-by-$$n$$ and $$R$$ is upper-triangular and $$n$$-by-$$n$$, then the singular values of $$R$$ are equal to the singular values of $$A$$. If $$A$$ is nonsingular, then

$$||{R}^{-1}|{|}_{2}=||({R}^{\prime}{)}^{-1}|{|}_{2}=\frac{1}{\mathrm{min}(\text{svd}(R))}=\frac{1}{\mathrm{min}(\text{svd}(A))}$$

**Upper Bound for R = Q'A**

The upper bound for the magnitude of the elements of $$R$$ is

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

**Proof of Upper Bound for R = Q'A**

The $$j$$th column of $$R$$ is equal to $$R(:,j)={Q}^{\prime}A(:,j)$$, so

$$\begin{array}{rcl}\mathrm{max}(|R(:,j)|)& =& ||R(:,j)|{|}_{\infty}\\ & \le & ||R(:,j)|{|}_{2}\\ & =& ||{Q}^{\prime}A(:,j)|{|}_{2}\\ & \le & ||{Q}^{\prime}|{|}_{2}||A(:,j)|{|}_{2}\\ & =& ||A(:,j)|{|}_{2}\\ & \le & \sqrt{m}||A(:,j)|{|}_{\infty}\\ & =& \sqrt{m}\mathrm{max}(|A(:,j)|)\\ & \le & \sqrt{m}\mathrm{max}(|A(:)|).\end{array}$$

Since $$\mathrm{max}(|R(:,j)|)\le \sqrt{m}\mathrm{max}(|A(:)|)$$ for all $$1\le j$$, then

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

**Upper Bound for C = Q'B**

The upper bound for the magnitude of the elements of $$C={Q}^{\prime}B$$ is

$$\mathrm{max}(|C(:)|)\le \sqrt{m}\mathrm{max}(|B(:)|)$$.

**Proof of Upper Bound for C = Q'B**

The proof of the upper bound for $$C={Q}^{\prime}B$$ is the same as the proof of the upper bound for $$R={Q}^{\prime}A$$ by substituting $$C$$ for $$R$$ and $$B$$ for $$A$$.

**Upper Bound for X = A\B**

The upper bound for the magnitude of the elements of $$X=A\backslash B$$ is

$$\mathrm{max}(|X(:)|)\le \frac{\sqrt{m}\mathrm{max}(|B(:)|)}{\mathrm{min}(\text{svd}(A))}$$.

**Proof of Upper Bound for X = A\B**

If $$A$$ is not full rank, then $$\mathrm{min}(\text{svd}(A))=0$$, and if $$B$$ is not equal to zero, then $$\sqrt{m}\mathrm{max}(|B(:)|)/\mathrm{min}(\text{svd}(A))=\infty $$ and so the inequality is true.

If $$A$$ is full rank, then $$x={R}^{-1}({Q}^{\prime}b)$$. Let $$x=X(:,j)$$ be the $$j$$th column of $$X$$, and $$b=B(:,j)$$ be the $$j$$th column of $$B$$. Then

$$\begin{array}{rcl}\mathrm{max}(|x(:)|)& =& ||x|{|}_{\infty}\\ & \le & ||x|{|}_{2}\\ & =& ||{R}^{-1}\cdot ({Q}^{\prime}b)|{|}_{2}\\ & \le & ||{R}^{-1}|{|}_{2}||{Q}^{\prime}|{|}_{2}||b|{|}_{2}\\ & =& (1/\mathrm{min}(\text{svd}(A)))\cdot 1\cdot ||b|{|}_{2}\\ & =& ||b|{|}_{2}/\mathrm{min}(\text{svd}(A))\\ & \le & \sqrt{m}||b|{|}_{\infty}/\mathrm{min}(\text{svd}(A))\\ & =& \sqrt{m}\mathrm{max}(|b(:)|)/\mathrm{min}(\text{svd}(A)).\end{array}$$

Since $$\mathrm{max}(|x(:)|)\le \sqrt{m}\mathrm{max}(|b(:)|)/\mathrm{min}(\text{svd}(A))$$ for all rows and columns of $$B$$ and $$X$$, then

$$\mathrm{max}(|X(:)|)\le \frac{\sqrt{m}\mathrm{max}(|B(:)|)}{\mathrm{min}(\text{svd}(A))}$$.

**Lower Bound for min(svd(A))**

You can estimate a lower bound $$s$$ of $$\mathrm{min}(\text{svd}(A))$$for complex-valued $$A$$ using the following formula,

$$s=\frac{{\sigma}_{N}}{\sqrt{2}}\sqrt{{\gamma}^{-1}(\frac{{p}_{s}\phantom{\rule{0.16666666666666666em}{0ex}}{\Gamma (m-n+2)}^{2}\phantom{\rule{0.16666666666666666em}{0ex}}\Gamma \left(n\right)}{\Gamma (m+1)\phantom{\rule{0.16666666666666666em}{0ex}}\Gamma (m-n+1)(m-n+1)},\phantom{\rule{0.2777777777777778em}{0ex}}m-n+1)}$$

where $${\sigma}_{N}$$ is the standard deviation of random noise added to the elements of $$A$$, $$1-{p}_{s}$$ is the probability that $$s\le \mathrm{min}(\text{svd}(A))$$, $$\Gamma $$ is the `gamma`

function, and $${\gamma}^{-1}$$is the inverse incomplete gamma function `gammaincinv`

.

The proof is found in [1]. It is derived by integrating the formula in Lemma 3.4 from [3] and rearranging terms.

Since $$s\le \mathrm{min}(\text{svd}(A))$$ with probability $$1-{p}_{s}$$, then you can bound the magnitude of the elements of $$X$$ without computing $$\text{svd}(A)$$,

$$\mathrm{max}(|X(:)|)\le \frac{\sqrt{m}\mathrm{max}(|B(:)|)}{\mathrm{min}(\text{svd}(A))}\le \frac{\sqrt{m}\mathrm{max}(|B(:)|)}{s}$$ with probability $$1-{p}_{s}$$.

You can compute $$s$$ using the `fixed.complexSingularValueLowerBound`

function which uses a default probability of 5 standard deviations below the mean, $${p}_{s}=(1+\text{erf}(-5/\sqrt{2}))/2\approx 2.8665\cdot 1{0}^{-7}$$, so the probability that the estimated bound for the smallest singular value $$s$$ is less than the actual smallest singular value of $$A$$ is $$1-{p}_{s}\approx 0.9999997$$.

**Example**

This example runs a simulation with many random matrices and compares the analytical bounds with the actual singular values of $$A$$ and the actual largest elements of $$R={Q}^{\prime}A$$, $$C={Q}^{\prime}B$$, and $$X=A\backslash B$$.

**Define System Parameters**

Define the matrix attributes and system parameters for this example.

`m`

is the number of rows in matrices `A`

and `B`

. 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 matrix `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}(A)$$ 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 standard deviation of the noise from quantizing the real and imaginary parts of a complex signal is $${2}^{-\text{precisionBits}}/\sqrt{6}$$ [4,5]. Use the `fixed.complexQuantizationNoiseStandardDeviation`

function 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 $${\sigma}_{\text{noise}}={\sigma}_{\text{thermal}\text{}\text{noise}}$$.

noiseStandardDeviation = thermalNoiseStandardDeviation;

Use `fixed.complexQRMatrixSolveFixedpointTypes`

to compute fixed-point types.

```
T = fixed.complexQRMatrixSolveFixedpointTypes(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}$ 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 transforming $\mathit{B}$ to ${\mathit{Q}}^{\prime}\mathit{B}$ in-place so that it does not overflow.

T.B

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

`T.X`

is the type computed for the solution $\mathit{X}=\mathit{A}\backslash \mathit{B}\text{\hspace{0.17em}}$so that there is a low probability that it overflows.

T.X

ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 37 FractionLength: 24

**Upper Bounds for R and C=Q'B**

The upper bounds for $$R$$ and $$C={Q}^{\prime}B$$ are computed using the following formulas, where $$m$$ is the number of rows of matrices $$A$$ and $$B$$.

$$\mathrm{max}(|R(:)|)\le \sqrt{m}\mathrm{max}(|A(:)|)$$

$$\mathrm{max}(|C(:)|)\le \sqrt{m}\mathrm{max}(|B(:)|)$$

These upper bounds are used to select a fixed-point type with the required number of bits of precision to avoid overflows.

upperBoundR = sqrt(m)*max_abs_A

upperBoundR = 24.4949

upperBoundQB = sqrt(m)*max_abs_B

upperBoundQB = 24.4949

**Lower Bound for min(svd(A)) for Complex A**

A lower bound for $$\mathrm{min}(\text{svd}(A))$$ is estimated by the `fixed.complexSingularValueLowerBound`

function using a probability that the estimate $$s$$ is not greater than the actual smallest singular value. The default probability is 5 standard deviations below the mean. You can change this probability by specifying it as the last input parameter to the `fixed.complexSingularValueLowerBound`

function.

estimatedSingularValueLowerBound = fixed.complexSingularValueLowerBound(m,n,noiseStandardDeviation)

estimatedSingularValueLowerBound = 0.0389

**Simulate and Compare to the Computed Bounds**

The bounds are within an order of magnitude of the simulated results. This is sufficient because the number of bits translates to a logarithmic scale relative to the range of values. Being within a factor of 10 is between 3 and 4 bits. This is a good starting point for specifying a fixed-point type. If you run the simulation for more samples, then it is more likely that the simulated results will be closer to the bound. This example uses a limited number of simulations so it doesn't take too long to run. For real-world system design, you should run additional simulations.

Define the number of samples, `numSamples`

, over which to run the simulation.

numSamples = 1e4;

Run the simulation.

```
[actualMaxR,actualMaxQB,singularValues,X_values] = runSimulations(m,n,p,rankA,max_abs_A,max_abs_B,...
numSamples,noiseStandardDeviation,T);
```

You can see that the upper bound on $$R$$ compared to the measured simulation results of the maximum value of $$R$$ over all runs is within an order of magnitude.

upperBoundR

upperBoundR = 24.4949

max(actualMaxR)

ans = 9.6720

You can see that the upper bound on $$C={Q}^{\prime}B$$ compared to the measured simulation results of the maximum value of $$C={Q}^{\prime}B$$ over all runs is also within an order of magnitude.

upperBoundQB

upperBoundQB = 24.4949

max(actualMaxQB)

ans = 4.4764

Finally, see that the estimated lower bound of $$\mathrm{min}(\text{svd}(A))$$ compared to the measured simulation results of $$\mathrm{min}(\text{svd}(A))$$ over all runs is also within an order of magnitude.

estimatedSingularValueLowerBound

estimatedSingularValueLowerBound = 0.0389

`actualSmallestSingularValue = min(singularValues,[],'all') `

actualSmallestSingularValue = 0.0443

Plot the distribution of the singular values over all simulation runs. The distributions of the largest singular values correspond to the signals that determine the rank of the matrix. The distributions of the smallest singular values correspond to the noise. The derivation of the estimated bound of the smallest singular value makes use of the random nature of the noise.

clf fixed.example.plot.singularValueDistribution(m,n,rankA,noiseStandardDeviation,... singularValues,estimatedSingularValueLowerBound,"complex");

Zoom in to the smallest singular value to see that the estimated bound is close to it.

xlim([estimatedSingularValueLowerBound*0.9, max(singularValues(n,:))]);

Estimate the largest value of the solution, X, and compare it to the largest value of X found during the simulation runs. The estimation is within an order of magnitude of the actual value, which is sufficient for estimating a fixed-point data type, because it is between 3 and 4 bits.

This example uses a limited number of simulation runs. With additional simulation runs, the actual largest value of X will approach the estimated largest value of X.

estimated_largest_X = fixed.complexMatrixSolveUpperBoundX(m,n,max_abs_B,noiseStandardDeviation)

estimated_largest_X = 629.3194

`actual_largest_X = max(abs(X_values),[],'all')`

actual_largest_X = 70.2644

Plot the distribution of X values and compare it to the estimated upper bound for X.

clf fixed.example.plot.xValueDistribution(m,n,rankA,noiseStandardDeviation,... X_values,estimated_largest_X,"complex normally distributed random");

**Supporting Functions**

The `runSimulations`

function creates a series of random matrices $$A$$ and $$B$$ of a given size and rank, quantizes them according to the computed types, computes the QR decomposition of $$A$$, and solves the equation $$AX=B$$. It returns the maximum values of $$R={Q}^{\prime}A$$ and $$C={Q}^{\prime}B$$, the singular values of $$A$$, and the values of $$X$$ so their distributions can be plotted and compared to the bounds.

function [actualMaxR,actualMaxQB,singularValues,X_values] = runSimulations(m,n,p,rankA,max_abs_A,max_abs_B,... numSamples,noiseStandardDeviation,T) precisionBits = T.A.FractionLength; A_WordLength = T.A.WordLength; B_WordLength = T.B.WordLength; actualMaxR = zeros(1,numSamples); actualMaxQB = zeros(1,numSamples); singularValues = zeros(n,numSamples); X_values = zeros(n,numSamples); for j = 1:numSamples A = (max_abs_A/sqrt(2))*fixed.example.complexRandomLowRankMatrix(m,n,rankA); % Adding normally distributed random noise makes A non-singular. A = A + fixed.example.complexNormalRandomArray(0,noiseStandardDeviation,m,n); A = quantizenumeric(A,1,A_WordLength,precisionBits); B = fixed.example.complexUniformRandomArray(-max_abs_B,max_abs_B,m,p); B = quantizenumeric(B,1,B_WordLength,precisionBits); [Q,R] = qr(A,0); C = Q'*B; X = R\C; actualMaxR(j) = max(abs(R(:))); actualMaxQB(j) = max(abs(C(:))); singularValues(:,j) = svd(A); X_values(:,j) = X; end end

**References**

Thomas A. Bryan and Jenna L. Warren. “Systems and Methods for Design Parameter Selection”. Patent pending. U.S. Patent Application No. 16/947,130. 2020.

Perform QR Factorization Using CORDIC. Derivation of the bound on growth when computing QR. MathWorks. 2010. url: https://www.mathworks.com/help/fixedpoint/ug/perform-qr-factorization-using-cordic.html.

Zizhong Chen and Jack J. Dongarra. “Condition Numbers of Gaussian Random Matrices”. In: SIAM J. Matrix Anal. Appl. 27.3 (July 2005), pp. 603–620. issn: 0895-4798. doi: 10.1137/040616413. url: https://dx.doi.org/10.1137/040616413.

Bernard Widrow. “A Study of Rough Amplitude Quantization by Means of Nyquist Sampling Theory”. In: IRE Transactions on Circuit Theory 3.4 (Dec. 1956), pp. 266–276.

Bernard Widrow and István Kollár. Quantization Noise – Roundoff Error in Digital Computation, Signal Processing, Control, and Communications. Cambridge, UK: Cambridge University Press, 2008.

Gene H. Golub and Charles F. Van Loan. Matrix Computations. Second edition. Baltimore: Johns Hopkins University Press, 1989.

Suppress mlint warnings in this file.

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

### Determine Fixed-Point Types for Complex Least-Squares Matrix Solve AX=B

This example shows how to use the `fixed.complexQRMatrixSolveFixedpointTypes`

function to analytically determine fixed-point types for the solution of the complex least-squares matrix equation $$AX=B$$, where $$A$$ is an $$m$$-by-$$n$$ matrix with $$m\ge n$$, $$B$$ is $$m$$-by-$$p$$, and $$X$$ is $$n$$-by-$$p$$.

Fixed-point types for the solution of the matrix equation $$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 [-1,1]$$, 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 matrices `A`

and `B`

. 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 matrix `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}(A)$$ 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 $${\sigma}_{\text{noise}}={\sigma}_{\text{thermal}\text{}\text{noise}}$$.

noiseStandardDeviation = thermalNoiseStandardDeviation;

Use `fixed.complexQRMatrixSolveFixedpointTypes`

to compute fixed-point types.

```
T = fixed.complexQRMatrixSolveFixedpointTypes(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 $$R={Q}^{\prime}A$$ in-place so that it does not overflow.

T.A

`T.B`

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

T.B

`T.X`

is the type computed for the solution $\mathit{X}=\mathit{A}\backslash \mathit{B}\text{\hspace{0.17em}}$so that there is a low probability that it overflows.

T.X

ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 37 FractionLength: 24

**Use the Specified Types to Solve the Matrix Equation AX=B**

Create random matrices `A`

and `B`

such that `B`

is in the range of `A`

, and `rankA=rank(A)`

. Add random measurement noise to `A`

which will make it become full rank, but it will also affect the solution so that `B`

is only close to the range of `A`

.

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

Cast the inputs to the types determined by `fixed.complexQRMatrixSolveFixedpointTypes`

. 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.qrMatrixSolve`

function by using `fiaccel`

to generate a MATLAB executable (MEX) function.

fiaccel fixed.qrMatrixSolve -args {A,B,T.X} -o qrComplexMatrixSolve_mex

Specify the output type `T.X`

and compute fixed-point $$X=A\backslash B$$ using the QR method.

X = qrComplexMatrixSolve_mex(A,B,T.X);

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

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

relative_error = 0.0056

Suppress `mlint`

warnings in this file.

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

### Determine Fixed-Point Types for Complex Least-Squares Matrix Solve with Tikhonov Regularization

This example shows how to use the `fixed.complexQRMatrixSolveFixedpointTypes`

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]X=\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right],$$

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

The least-squares solution is

$${X}_{LS}=({\lambda}^{2}{I}_{n}+{A}^{T}A{)}^{-1}{A}^{T}B$$

but is computed without squares or inverses.

**Define System Parameters**

Define the matrix attributes and system parameters for this example.

`m`

is the number of rows in matrices `A`

and `B`

. 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 matrix `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;

`A`

to be less than the number of columns. In a problem such as beamforming or direction finding, $$\text{rank}(A)$$ 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;

`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);

`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**

Set $${\sigma}_{\text{noise}}={\sigma}_{\text{thermal}\text{}\text{noise}}$$.

noiseStandardDeviation = thermalNoiseStandardDeviation;

Use `fixed.complexQRMatrixSolveFixedpointTypes`

to compute fixed-point types.

```
T = fixed.complexQRMatrixSolveFixedpointTypes(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}^{T}\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 transforming $$\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$ to $$C={Q}^{T}\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$ in-place so that it does not overflow.

T.B

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

`T.X`

is the type computed for the solution $$X=\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]\backslash \left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$, so that there is a low probability that it overflows.

T.X

ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 44 FractionLength: 32

**Use the Specified Types to Solve the Matrix Equation**

Create random matrices `A`

and `B`

such that `B`

is in the range of `A`

, and `rankA=rank(A)`

. Add random measurement noise to `A`

which will make it become full rank, but it will also affect the solution so that `B`

is only close to the range of `A`

.

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

Cast the inputs to the types determined by `fixed.complexQRMatrixSolveFixedpointTypes`

. Quantizing to fixed-point is equivalent to adding random noise [4,5].

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

Accelerate the `fixed.qrMatrixSolve`

function by using `fiaccel`

to generate a MATLAB executable (MEX) function.

fiaccel fixed.qrMatrixSolve -args {A,B,T.X,regularizationParameter} -o qrMatrixSolve_mex

Specify output type `T.X`

and compute fixed-point $$X=A\backslash B$$ using the QR method.

X = qrMatrixSolve_mex(A,B,T.X,regularizationParameter);

**Verify the Accuracy of the Output**

Verify that the relative error between the fixed-point output and the output from MATLAB using the default double-precision floating-point values is small.

$${X}_{\text{double}}=\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]\backslash \left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$

A_lambda = double([regularizationParameter*eye(n);A]); B_0 = [zeros(n,p);double(B)]; X_double = A_lambda\B_0; relativeError = norm(X_double - double(X))/norm(X_double)

relativeError = 5.2634e-06

Suppress `mlint`

warnings in this file.

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

## Input Arguments

`m`

— Number of rows in *A* and *B*

positive integer-valued scalar

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

**Data Types: **`double`

`n`

— Number of columns in *A*

positive integer-valued scalar

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

**Data Types: **`double`

`max_abs_A`

— Maximum of absolute value of *A*

scalar

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

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

**Data Types: **`double`

`max_abs_B`

— Maximum of absolute value of *B*

scalar

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

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

**Data Types: **`double`

`precisionBits`

— Required number of bits of precision

positive integer-valued scalar

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

**Data Types: **`double`

`noiseStandardDeviation`

— Standard deviation of additive random noise in *A*

scalar

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`

`p_s`

— Probability that estimate of lower bound *s* is larger than the actual smallest singular value of the matrix

`≈3·10`^{-7}

(default) | scalar

^{-7}

Probability that estimate of lower bound *s* is larger than the
actual smallest singular value of the 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-*p _{s}* ≈ 0.9999997.

**Data Types: **`double`

`regularizationParameter`

— Regularization parameter

`0`

(default) | nonnegative scalar

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 least-squares problem $$\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]X=\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$$.

**Data Types: **`single`

| `double`

| `int8`

| `int16`

| `int32`

| `int64`

| `uint8`

| `uint16`

| `uint32`

| `uint64`

| `fi`

`maxWordLength`

— Maximum word length of fixed-point types

`128`

(default) | positive integer

Maximum word length of fixed-point types, specified as a positive integer.

If the word length of the fixed-point type exceeds the specified maximum word
length, the default of `128`

bits is used.

**Data Types: **`single`

| `double`

| `int8`

| `int16`

| `int32`

| `int64`

| `uint8`

| `uint16`

| `uint32`

| `uint64`

| `fi`

## Output Arguments

`T`

— Fixed-point types for *A*, *B*, and *X*

struct

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*and transforms*B*in-place into*C*=*Q*'*B*, where*Q**R*=*A*is the QR decomposition of*A*.*X*such that there is a low probability of overflow.

## Tips

Use `fixed.complexQRMatrixSolveFixedpointTypes`

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

## Algorithms

`T.A`

and `T.B`

are computed using `fixed.qrFixedpointTypes`

. The number of integer bits required to prevent overflow
is derived from the following bounds on the growth of *R* and *C*=*Q*'*B* [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(\left|R(:)\right|\right)\le \sqrt{m}\mathrm{max}\left(\left|A(:)\right|\right).$$

The elements of *C*=*Q*'*B* are bounded in magnitude by

$$\mathrm{max}\left(\left|C(:)\right|\right)\le \sqrt{m}\mathrm{max}\left(\left|B(:)\right|\right).$$

`T.X`

is computed by bounding the output, *X*, in the
least-squares solution of *A**X*=*B* using the following formula [3] [4].

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

$$\mathrm{max}\left(\left|X(:)\right|\right)\le \frac{\sqrt{m}\mathrm{max}\left(\left|B(:)\right|\right)}{\mathrm{min}\left(\text{svd}\left(A\right)\right)}.$$

Computing the singular value decomposition to derive the above bound on
*X* is more computationally expensive 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.

[3] Bryan, Thomas A. and Jenna L. Warren. "Systems and Methods for Design Parameter Selection." U.S. Patent Application No. 16/947, 130. 2020.

[4] Chen, Zizhong and Jack J.
Dongarra. "Condition Numbers of Gaussian Random Matrices." *SIAM Journal on Matrix
Analysis and Applications* 27, no. 3 (July 2005): 603-620.

## Version History

**Introduced in R2021b**

### R2022b: Support for maximum word length

You can now use the `maxWordLenth`

parameter to specify the maximum
word length of the fixed-point types.

### R2022a: Support for Tikhonov regularization parameter

The `fixed.complexQRMatrixSolveFixedpointTypes`

function now supports
the Tikhonov regularization parameter, regularizationParameter.

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)