text:
# Difference between revisions of "Split group"

over a field $k$ , $k$ - split group

A linear algebraic group defined over $k$ and containing a Borel subgroup that is split over $k$ . Here a connected solvable linear algebraic group $B$ is called split over $k$ if it is defined over $k$ and has a composition series (cf. Composition sequence) $B = B _{0} \supset B _{1} \supset \dots \supset B _{t} = \{ 1 \}$ such that the $B _{i}$ are connected algebraic subgroups defined over $k$ and each quotient group $B _{i} /B _ {i + 1}$ is isomorphic over $k$ to either a one-dimensional torus $G _{m} \cong \mathop{\rm GL}\nolimits _{1}$ or to the additive one-dimensional group $G _{a}$ . In particular, an algebraic torus is split over $k$ if and only if it is defined over $k$ and is isomorphic over $k$ to the direct product of copies of the group $G _{m}$ . For connected solvable $k$ - split groups the Borel fixed-point theorem holds. A reductive linear algebraic group defined over $k$ is split over $k$ if and only if it has a maximal torus split over $k$ , that is, if its $k$ - rank coincides with its rank (see Rank of an algebraic group; Reductive group). The image of a $k$ - split group under any rational homomorphism defined over $k$ is a $k$ - split group. Every linear algebraic group $G$ defined over a field $k$ is split over an algebraic closure of $k$ ; if $G$ is also reductive or solvable and connected, then it is split over some finite extension of $k$ . If $k$ is a perfect field, then a connected solvable linear algebraic group defined over $k$ is split over $k$ if and only if it can be reduced to triangular form over $k$ . If $\mathop{\rm char}\nolimits \ k = 0$ , then a linear algebraic group defined over $k$ is split over $k$ if and only if its Lie algebra $L$ is a split (or decomposable) Lie algebra over $k$ ; by definition, the latter means that the Lie algebra $L$ has a split Cartan subalgebra, that is, a Cartan subalgebra $H \subset L$ for which all eigenvalues of every operator $\mathop{\rm ad}\nolimits _{L} \ h$ , $h \in H$ , belong to $k$ .

If $G _ {\mathbf R}$ is the real Lie group of real points of a semi-simple $\mathbf R$ - split algebraic group $G$ and if $G _ {\mathbf C}$ is the complexification of the Lie group $G _ {\mathbf R}$ , then $G _ {\mathbf R}$ is called a normal real form of the complex Lie group $G _ {\mathbf C}$ .

There exist quasi-split groups (cf. Quasi-split group) over a field $k$ that are not split groups over $k$ ; the group $\mathop{\rm SO}\nolimits (3,\ 1)$ is an example for $k = \mathbf R$ .

#### References

 [1] A. Borel, "Linear algebraic groups" , Benjamin (1969) MR0251042 Zbl 0206.49801 Zbl 0186.33201 [2] A. Borel, J. Tits, "Groupes réductifs" Publ. Math. IHES , 27 (1965) pp. 55–150 MR0207712 Zbl 0145.17402 [3] Yu.I. Merzlyakov, "Rational groups" , Moscow (1980) (In Russian) MR0602700 Zbl 0518.20032 [4] J.E. Humphreys, "Linear algebraic groups" , Springer (1975) MR0396773 Zbl 0325.20039
How to Cite This Entry:
Split group. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Split_group&oldid=44286
This article was adapted from an original article by V.L. Popov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article


text:
# The matrix of a linear transformation

#### Everything You Need in One Place

Homework problems? Exam preparation? Trying to grasp a concept or just brushing up the basics? Our extensive help & practice library have got you covered.

#### Learn and Practice With Ease

Our proven video lessons ease you through problems quickly, and you get tonnes of friendly practice on questions that trip students up on tests and finals.

#### Instant and Unlimited Help

Our personalized learning platform enables you to instantly find the exact walkthrough to your specific type of question. Activate unlimited help now!

##### Intros
###### Lessons
1. The Matrix of a Linear Transformation Overview:
2. The Standard Basis and Matrix
$T(x)=Ax, A$: The Standard Matrix
$\Bbb{R}^2$ standard Basis: and
$\Bbb{R}^3$ standard Basis:
• Transformed standard basis
• Finding the Standard Matrix
3. Finding the Standard Matrix Geometrically in $\Bbb{R}^2$
• Drawing the Standard basis on a Graph
• Identifying the Transformed Standard Basis
• Combining the Standard Basis' into a Matrix
4. Types of Geometric Linear Transformations in $\Bbb{R}^2$
• Reflections on a Line
• Horizontal Expansion/Contraction
• Vertical Expansion/Contraction
• Horizontal & Vertical Shears
• Projections
• Rotation Transformations
##### Examples
###### Lessons
1. Finding the Standard Matrix with Transformed Basis
Assume that $T$ is a linear transformation. Find the standard matrix of $T$ if where and .
1. Assume that $T$ is a linear transformation. Find the standard matrix of $T$ if where and .
1. Finding the Standard Matrix Geometrically
Assume that $T$ is a linear transformation. Find the standard matrix of $T$ if $T: \Bbb{R}^2$$\Bbb{R}^2$ is a vertical shear transformation that maps $e_1$ to $e_1+2e_2$ and leaves $e_2$ unchanged.
1. Assume that $T$ is a linear transformation. Find the standard matrix of $T$ if $T: \Bbb{R}^2$$\Bbb{R}^2$ first performs a $x_2=x_1$ reflection, and then a $x_1$ reflection.
1. Finding the Matrix Algebraically
Show that $T$ is a linear transformation by finding a matrix $A$ that implements the mapping:
1. Finding for x given the Transformation
Let $T: \Bbb{R}^2$$\Bbb{R}^2$ be a linear transformation such that . Find a $x$ such that

### The matrix of a linear transformation

#### What is a linear transformation

From our lesson on the image and range of linear transformations we learnt that a linear transformation is a technique in which a vector gets "converted" into another by keeping a unique element from each of the original vector and assigning it into the resulting vector. This process basically maps one vector space into another. There may be different kinds of transformations in mathematics but the case of a linear transformation in linear algebra is that which preserves linear combinations from the original expression to the resulting one, in simple words, it preserves the way addition and scalar multiplication operate from the original vector to the transformed vector. A linear transformation example can also be called linear mapping since we are keeping the original elements from the original vector and just creating an image of it.

Recall the matrix equation Ax=b, normally, we say that the product of $A$ and $x$ gives $b$. Now we are going to say that A is a linear transformation matrix that transforms a vector x into a vector $b$ (we now call $b$ an image of a linear transformation of $x$).

In a sense $Ax$ is a function where if we plug in a vector, then it spits out another vector. If we call this function $T(x)$, then $T(x)=Ax$, where $T$ is the transformation. Note that $T(x)$ is an image of $x$ since $T(x)=b$;

#### The matrix of a linear transformation

So, let us define once more a linear transformation in mathematical form:

Where $T(x)$ is read as "the transformation of $x$", $x$ is the initial vector, and $A$ is the transformation matrix. We will focus on this $A$ this is what we call: the standard matrix of a linear transformation.

During this lesson, we will focus on methods to solve for the standard matrix A when you are given a linear transformation of a vector.

Let us start by describing the three main methods we use to solve such problems and then we will jump into examples of such exercises.

#### How to find the standard matrix of a linear transformation

There are three methods we can use to obtain the standard matrix of a linear transformation:

• Calculating the standard matrix using the transformed basis:

For a two dimensional basis, when using this method, we are provided with the unit vectors $e_{1}$ and $e_{2}$ and with the transformed basis vectors $T(e_{1})$ and $T(e_{2})$ to start with. If we are talking about a three-dimensional basis then we are provided with the unit vectors $e_{1}, e_{2}$ and $e_{3}$ and the transformed vectors $T(e_{1})$, $T(e_{2})$ and $T(e_{3})$. Then, the steps to follow to obtain the standard matrix are:

1. Use the definition of a linear transformation: $T(x)=Ax$ and define the vector $x$.
2. Expand vector $x$ into its components until is written in terms of the unit vectors and its variables $x_{1}, x_{2},..., x_{n}$.
3. Use the expansion of vector $x$ and perform the linear transformation $T(x)=Ax$.
4. Expand the transformation $T(x)$ until is in terms of the transformed vectors $T(e_{1})$, $T(e_{2})$ , ... , $T(e_{n})$ and the variables $x_{1}, x_{2},..., x_{n}$.
5. Then rewrite this expression from the transformation as the matrix multiplication $Ax$.
6. You have found the matrix $A$.

Notice that the standard matrix found is composed of the transformed vectors $T(e_{1})$, $T(e_{2})$ , ... , $T(e_{n})$. Technically, you could very well skip this whole process and just write down the matrix using the provided transformed vectors, BUT, you need to know how they were derived (plus your teacher may not accept this solution without an explanation). So make sure you understand the whole process.
Examples of this method are found in example exercises 1 and 2 in our next section.

• Finding the standard matrix geometrically:

To find a standard matrix geometrically means to find it using a cartesian coordinates graph, actually draw the vectors involved, see the transformations they go through and obtain from the result a new matrix: the standard matrix. The steps to follow to find a standard matrix geometrically for a two-dimensional basis are:

1. Draw the standard basis $e_{1}$ and $e_{2}$ in the $x_{1}x_{2}-plane$.
2. Obtain the transformed vectors $T(e_{1})$ and $T(e_{2})$.
3. Draw the transformed vectors using the information provided in the problem.
4. Combine the transformed vectors to produce the standard matrix.

Notice that are providing the steps for a two-dimensional basis only, since we can a two-dimensional coordinate plane only (actually, you can also draw a three-dimensional plane, but it gets a bit complicated. Further than three dimensions we cannot draw them, and so, we use other techniques to solve for transformations with such bases).
For a step by step explanation on how to use this method, look at example 3 in our last section for this lesson.

• Computing the standard matrix algebraically:

The algebraic computation in order to find the standard matrix of a linear transformation can be done easily when the problem provides the complete expression for the linear transformation $T(x)=Ax$. In other words, once you have the initial vector x and the final vector $Ax$, you can use these expressions to solve for the matrix $A$.
The steps to follow in order to solve a problem this way are:

1. Expand the given expression of the linear transformation resulting vector into an addition of vectors for each of the different variables inside.
2. Factor out the variables $x_{1}, x_{2},..., x_{n}$ from each of the column vectors.
3. Form a matrix multiplication by rearranging the resulting column vectors from our last step into a matrix, and then multiplying it for the vector x which is the column vector containing all of the variables $x_{1}, x_{2},..., x_{n}$.
4. The matrix that was formed in our last step is the standard matrix of the linear transformation.

An example of this process can be seen in the exercise example 4 in our next section.
Notice that this is probably the simplest methods to use, and if you are given all of the necessary information and have to be time-effective while solving an exercise on this, we recommend you to use this method.

#### Linear transformation matrix examples

During the first two examples we will be finding the Standard Matrix using a transformed basis, then we will see two examples on how to find the standard matrix geometrically. We finish off with an example where we will compute the standard matrix algebraically.

#### Example 1

Assume that $T$ is a linear transformation. Find the matrix representation of linear transformation $T$ (the standard matrix) if:

Where the unit vectors are defined as follows:

To answer this question we could literally just take the vectors resulting from the linear transformation of the unit vectors $e_{1}$ and $e_{2}$, put them together into a matrix and that would be our standard matrix, but how does that work? Let us derive it then!

We know that a linear transformation of a matrix $A$ has the form: $T(x)=Ax$, therefore, we need a vector $x$ to perform the transformation. For this case our vector $x$ must have two entries, and so, vector $x$ is (notice this is just any vector $x$ in two dimensions):

We can expand this vector x into an addition of vectors and factor out their components in order to have the unit vectors which form part of it visible, just look at how we have expanded it below:

And now, it can clearly be seen how the vector x is composed by the variables $x_{1}$ and $x_{2}$, and the set of unit vectors $e_{1}$ and $e_{2}$. Thus we can rewrite this last equation as:

So we take the linear transformation of vector $x$ which goes as:

Notice how the linear transformation affects the unit vectors only, this is because those are the ones establishing the direction of the vector and a linear transformation usually changes that (remember it can rescale a vector too, but the most common cases it preserves its magnitude, but rotates it with respect of a certain axes). So, since we know what T($e_{1}$) and T($e_{2}$) are we can rewrite the transformation as:

Where the standard matrix of a linear transformation as the one represented in equation 2 is:

#### Example 2

Assume that $T$ is a linear transformation. Find the standard matrix of linear transformation $T$ if:

where the unit vectors are defined as:

A linear transformation of a matrix $A$ has the form: $T(x)=Ax$, thus, we start by expanding the vector $x$ into its components once more:

We can observe how vector $x$ is composed by the variables $x_{1}, x_{2}$ and $x_{3}$, and the set of unit vectors $e_{1}, e_{2}$ and $e_{3}$. Thus we can rewrite this last equation as:

So we take the linear transformation of vector x which goes as:

Since we know what T($e_{1}$), T($e_{2}$) and T($e_{3}$) are we can rewrite the transformation as:

And so, the standard matrix is:

#### Example 3

Assume that $T$ is a linear transformation. Find the matrix of the linear transformation $T$ if $T$: $R^{2} \to R^{2}$ is a vertical shear transformation that maps $e_{1}$ to $e_{1}+2e_{2}$ and leaves $e_{2}$ unchanged.
Let us first define the standard basis for this problem, given that we are talking of a 2-dimensional vector space $R^{2}$, then this means our standard basis unit vectors are:

For this example we will use the steps summarized on the method to find a standard matrix geometrically:

1. $\quad$ Draw the standard basis $e_{1}$ and $e_{2}$ in the $x_{1}x_{2}-plane$.

2. $\quad$ Obtain the transformed vectors $T(e_{1}$) and $T(e_{2}$).

The transformation provided is defined as: $e_{1}$ to $e_{1}+2e_{2}$ and $e_{2}$ unchanged. Using the standard basis unit vectors we can define the transformations as:

Notice that $T(e_{2}) = e_{2}$ because the transformation is defined to leave the basis unchanged.

3. $\quad$ Draw the transformed vectors using the information provided in the problem.

4. $\quad$ Combine the the transformed vectors to produce the standard matrix.

#### Example 4

Show that $T$ is a linear transformation by finding a matrix $A$ that implements the mapping:

This is the easiest method to use when given the linear transformation definition, the only thing to do is to separate the vector given into its variables' individual vectors:

We can rewrite the transformation above as follows, by factoring out of the column vectors the variables $x_{1}$, $x_{2}$ and $x_{3}$:

And so, now we can see how the transformation fits with the formula for a linear transformation $T(x)=Ax$ by rewriting it once more as the appropriate matrix multiplication of $A$ and the column vector $x$:

Therefore, the linear transformation matrix, or standard matrix $A$ is:

***

Now that you have learnt how to compute linear transformations and their corresponding standard matrices, we would like to finalize our lesson be recommending you to take a look into this lesson on linear transformations from $R^{n}$ to $R^{m}$, where you can see some more examples and graphs with the transformations explained. We also recommend this lesson named Google search since it goes even deeper on the subject matter by introducing some calculus level computations and linear transformation applications.

So, this is it for our lesson of today, we hope you enjoyed it. Make sure to work through the exercises and see you on the next one!
The standard basis, $e_1$ and $e_2$, are unit vectors in $\Bbb{R}^2$ such that:
If are the transformed vectors, then the standard matrix is

Why does that work? Watch the intro video

The standard basis, $e_1$, $e_2$, and $e_3$ are unit vectors in $\Bbb{R}^3$ such that:

If are the transformed vectors, then the standard matrix is

To find the standard basis in $\Bbb{R}^2$ geometrically in a graph we:
1. Draw the standard basis $e_1$ and $e_2$ in the $x_1 x_2$ plane
2. Draw the transformed vectors using the information given
3. Identify the transformed vectors $T(e_1)$, and $T(e_2)$.
4. Combine them to get the standard matrix

Here are the many types of transformations you may see in this section:

Reflections

Vertical/Horizontal Expansions and contractions

Vertical/Horizontal Shears

Projections

Circle Rotation

format: plain


text:
# Linear Regression Calculator

Created by Anna Szczepanek, PhD
Reviewed by Dominik Czernia, PhD and Jack Bowater
Last updated: Feb 02, 2023

Table of contents:

With the help of our linear regression calculator, you can quickly determine the simple linear regression equation for any set of data points.

What is linear regression?, you wonder. Scroll down to learn what the linear regression model is, what the linear regression definition looks like, and how to calculate the linear regression formula by hand. You will also find an example of linear regression and a detailed explanation of how to interpret the slope of the regression line!

## What is linear regression?

Linear regression is a statistical technique that aims to model the relationship between two variables (one variable is called explanatory/independent and the other is dependent) by determining a linear equation that best predicts the values of the dependent variable based on the values of the independent variable.

In other words, when we have a set of two-dimensional data points, linear regression describes the (non-vertical) straight line that best fits these points. A simple example is when we want to predict the weights of students based on their heights, or in chemistry, where linear regression is used in the calculation of the concentration of an unknown sample.

Be careful, as in some situations simple linear regression may not be the right model! If your data seem to follow a parabola rather than a straight line, then you should try using our quadratic regression calculator, if they rather resemble a cubic (degree three) curve, try the cubic regression calculator, while if your data come from a process characterized by exponential growth, try the exponential regression calculator instead.

## Linear regression equation

It's time for a more formal definition of linear regression. Assume we are given a set of points in the Cartesian plane:

(x1,y1), ..., (xn,yn).

We assume that x is an independent variable, and that y is a dependent variable. We are going to find a straight non-vertical line with a slope a, and an intercept b, i.e., the line of the best fit has the formula:

y = a * x + b.

As you can see, it is really easy to write down the linear regression equation! When calculating linear regression, we need to work out the values of the parameters a and b. In the next section, we will explain how to interpret these parameters, and then we will show you how to calculate them efficiently.

⚠ Bear in mind that in this article we restrict our attention to the case with only one explanatory variable. We call such a model simple linear regression. If there are multiple explanatory variables, we call the model multiple linear regression.

💡 Simple linear regression is, well, simpler to understand and compute than multiple regression. However, many real-world phenomena require multiple explanatory variables. We will show you a way to calculate simple linear regression which easily extends to multiple linear regression.

## Linear regression parameters interpretation

#### The slope coefficient

The coefficient a is the slope of the regression line. It describes how much the dependent variable y changes (on average!) when the incoefficient of determination**, dependent variable x changes by one unit**. Indeed, let's take a look at the following simple calculation:

a * (x + 1) + b = (a * x + b) + a = y + a.

• If a > 0, then y increases by a units whenever x increases by 1 unit. We say there is a positive relationship between the two variables: as one increases, the other increases as well.
• If a < 0, then y decreases by a units whenever x increases by 1 unit. We say there is a negative relationship between the two variables: as one increases, the other decreases.
• If a = 0, then there is no relationship between the two variables in question: the value of y is the same (constant) for all values of x.

Interestingly, we can express the slope a in terms of the standard deviations of x and y and of their Pearson correlation. We have:

a = corr(x, y) ⋅ sd(y) / sd(x)

where:

• corr(x, y) is the correlation between x and y;
• sd(x) is the standard deviation of x; and
• sd(y) is the standard deviation of y.

#### The intercept coefficient

It isn't hard to note that the intercept coefficient b indicates the point on the vertical axis through which the fitted line passes. It has one more interesting property, which is related to the mean values of our observations.

Namely, the intercept coefficient b is such that the regression line passes through the point whose horizontal coefficient is equal to the mean of the x values, and the vertical coefficient is equal to the mean of the y values.

We call such a point the center of mass of the set of data points.

## How to use this linear regression calculator?

To use the linear regression calculator, follow the steps below:

1. Enter your data, up to 30 points. The calculator needs at least 3 points to fit the linear regression model to your data points.
2. We will show you the scatter plot of your data with the regression line.
3. Below the plot you can find the linear regression equation for your data.
4. Moreover, we tell you the of the fitted model. It tells you what proportion of the variance in the dependent variable y is explained by the model. Recall that R² ranges from 0 to 1, and the closer it is to 1, the better the fit. If you don't know what the coefficient of determination R² is, check the R squared calculator.
5. If you want to increase the precision of calculations, go to the advanced mode of our linear regression calculator. There you can set the number of significant figures.

Keep in mind that our linear regression calculator does not verify the assumptions of linear regression! You have to check them by yourself - at least remember to take a look at residuals to verify if they are independent, normally distributed, and homoscedastic (i.e., whether they have constant variance).

## How to calculate linear regression?

We will show you how to calculate linear regression using the orthogonal projection approach. This approach is very handful as the calculations are quick and it easily generalizes to multiple linear regression.

We need to introduce some notation.
First, let X be a matrix with two columns and n rows, where n is the number of data points. We fill the first column with ones, and in the second we put the observed values x1, ..., xn of the explanatory variable:

$\small \begin{bmatrix} 1 & x_1\\ 1& x_2\\ \vdots & \vdots \\ 1 & x_n \\ \end{bmatrix}$

Next, let y be a column vector filled with the values y1, ..., yn of the dependent variable:

$\small \begin{bmatrix} y_1\\ y_2\\ \ldots \\ y_n \\ \end{bmatrix}$

Finally, let β denote the column vector of the linear regression coefficients:

$\small \begin{bmatrix} a\\ b\\ \end{bmatrix}$

Note that the intercept occupies the first row, and the slope of the regression line the second row!

To find the vector β you just need to perform the following matrix multiplication:

β =(XTX)-1XTy

where:

• XT is the transpose of X

• (XTX)-1 is the inverse of **XTX

⚠ We assume that the inverse of XTX exists. In other words, that the columns of XTX are linearly independent. In our specific case of simple linear regression, this condition means that the observed values x1, ..., xn of the explanatory variable must not all be equal. Otherwise, we wouldn't be able to fit the linear regression.

💡 To compute multiple regression, you just need to append additional columns to the matrix X: each column must contain the observed values of a different explanatory variable. Obviously, the vector β contains then more coefficients: the number of coefficients is equal to the number of explanatory variables plus one. Most importantly, the matrix formula for β remains the same! That's the power of the matrix approach to linear regression!

## Linear regression example

We want to find the linear regression model for the observations:

(1, 3), (2, 6), (3, 6).

Our data is:

$\small X = \begin{bmatrix} 1 & 1 \\ 1 & 2\\ 1 & 3 \\ \end{bmatrix}$
$\small y = \begin{bmatrix} 3 \\ 6\\ 6 \\ \end{bmatrix}$

So, to find the linear regression model we need to:

Determine XT:

$\small \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ \end{bmatrix}$

Compute XTX:

$\small \begin{bmatrix} 3 & 6 \\ 6 & 14 \\ \end{bmatrix}$

Find (XTX)-1:

$\small \begin{bmatrix} \frac{14}{6} & -1 \\ -1 & \frac 12\\ \end{bmatrix}$

Perform the final matrix multiplication (XTX)-1XTy. The linear regression coefficients we wanted to find are:

$\small \begin{bmatrix} 2\\ 1.5\\ \end{bmatrix}$

Therefore, the slope of the regression line is 1.5 and the intercept is 2. The linear regression model for our data is:
y = 1.5x + 2

As you can see, to find the simple linear regression formula by hand, we need to perform a lot of computations. Thankfully, there is Omni's linear regression calculator! 😊

Anna Szczepanek, PhD
Linear model y = ax + b
Data (You may enter up to 30 points)
x₁
y₁
x₂
y₂
Enter at least 3 points (both x and y coordinates) to get your model.
People also viewed…

### 4 sided dice roller

Set up to 15 dice to roll with our 4-sided dice roller calculator.

### Circumference

Use this free circumference calculator to find the area, circumference and diameter of a circle.

### D20 dice roller

Roll online multiple D20 dice for Dungeons & Dragons or any tabletop game with our D20 dice roller calculator.

### Titration

Use our titration calculator to determine the molarity of your solution.


text:
InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Mathematics » "Bayesian Inference", book edited by Javier Prieto Tejedor, ISBN 978-953-51-3578-4, Print ISBN 978-953-51-3577-7, Published: November 2, 2017 under CC BY 3.0 license. © The Author(s).

# Sparsity in Bayesian Signal Estimation

By Ishan Wickramasingha, Michael Sobhy and Sherif S. Sherif
DOI: 10.5772/intechopen.70529

Article top

## Overview

Figure 1. Linear system with noisy output measurement.

Figure 2. Signal estimation using prior information.

Figure 3. A sinusoid in time and frequency domains.

Figure 4. Two-dimensional unit ball using different (pseudo)norms. (a) L0, (b) L0−1, and (c) L1.

Figure 5. Regularized least squares using L0.

Figure 6. Regularized least squares using L1.

Figure 7. Regularized least squares using L0−1.

Figure 8. Product of two student-t probability distributions.

# Sparsity in Bayesian Signal Estimation

Ishan Wickramasingha1, Michael Sobhy2 and Sherif S. Sherif1
Show details

## Abstract

In this chapter, we describe different methods to estimate an unknown signal from its linear measurements. We focus on the underdetermined case where the number of measurements is less than the dimension of the unknown signal. We introduce the concept of signal sparsity and describe how it could be used as prior information for either regularized least squares or Bayesian signal estimation. We discuss compressed sensing and sparse signal representation as examples where these sparse signal estimation methods could be applied.

Keywords: inverse problems, signal estimation, regularization, Bayesian methods, signal sparsity

## 1. Introduction

In engineering and science, a system typically refers to a physical process whose outputs are generated due to some inputs [1, 2]. Examples of systems include measuring instruments, imaging devices, mechanical and biomedical devices, chemical reactors and others. A system could be abstracted as a block diagram,

where x and y represent the inputs and outputs of the system, respectively. The block, A, formalizes the relation between these inputs and the outputs using mathematical equations [2, 3]. Depending on the nature of the system, the relation between its inputs and outputs could be either linear or nonlinear. For a linear relation, the system is called a linear system and it would be represented by a set of linear equations [3, 4]

 y=Ax. (1)

In this chapter, we will restrict our attention to linear systems, as they could adequately represent many actual systems in a mathematically tractable way.

When dealing with systems, two typical types of problems arise, forward and inverse problems.

### 1.1. Forward problems

In a forward problem, one would be interested in obtaining the output of a system due to a particular input [5, 6]. For linear systems, this output is the result of a simple matrix-vector product, Ax. Forward problems usually become more difficult as the number of equations increases or as uncertainties about the inputs, or the behavior of the system, are present [6].

### 1.2. Inverse problems

In an inverse problem, one would be interested in inferring the inputs to a system x that resulted in observed outputs, i.e., measured y [5, 6]. Another formulation of an inverse problem is to identify the behavior of the system, i.e., construct A, from knowledge of different input and output values. This problem formulation is known as system identification [1, 7, 8]. In this chapter, we will only consider the input inference problem. The nature of the input x to be inferred further leads to two broad categories of this problem: estimation, and classification. In input estimation, the input could assume an infinite number of possible values [4, 9], while in input classification the input could assume only a finite number (usually small) of possible values [4, 9]. Accordingly, in input classification, one would like to only assign an input to a predetermined signal class. In this chapter, we will only focus on estimation problems, particularly on restoring an input signal x from noisy data y that is obtained using a linear measuring system represented by a matrix A.

## 2. Signal restoration as example of an inverse problem

To solve the above signal restoration problem, we need to estimate input signal x through the inversion of matrix A. This could be a hard problem because in many cases the inverse of A might not exist, or the measurement data, y, might be corrupted by noise. The existence of the inverse of A depends on the number of acquired independent measurements relative to the dimension of the unknown signal [5, 10]. The conditions for the existence of a stable solution of any inverse problem, i.e., for an inverse problem to be well-posed, have been addressed by Hadamard as:

• Existence: for measured output y there exists at least one corresponding input x.

• Uniqueness: for measured output y there exists only one corresponding input x.

• Continuity: as the input x changes slightly, the output y changes slightly, i.e., the relation between x and y is continuous.

These conditions could be applied to linear systems as conditions on the matrix A. Let the matrix ARn×m, such that Rn×m denotes the set of matrices of dimension n × m with its elements being real values. The matrix equation, yn × 1 = An × m xm × 1, is equivalent to n linear equations with m unknowns. The matrix A is a linear transformation that maps input signals from its domain DA=Rm to its range RA=Rn [4, 5, 10]. For any measured output signal yRn, we could identify three cases based on the values of n and m.

### 2.1. Underdetermined linear systems

In this case, n < m, i.e., the number of equations is less than the number of unknowns,

 A=a11a12⋯a1m⋮⋮⋱⋮an1an2⋯anm. (2)

If these equations are consistent, Hadamard’s Existence condition will be satisfied. However, Hadamard’s Uniqueness condition is not satisfied because the Null Space(A) ≠ {0}, i.e., there exist z ≠ 0 ∈ Null Space(A) such that,

 Ax+z=y. (3)

This linear system is called under-determined because its equations, i.e., system constraints, are not enough to uniquely determine x [4, 5]. Thus, the inverse of A does not exist.

### 2.2. Overdetermined linear systems

In this case, m > n, the number of equations is more than the number of unknowns,

 A=a11a21⋯⋯a1ma2m⋮⋮⋱⋮⋮an1⋯anm. (4)

If these equations are consistent, Hadamard’s Existence condition will not be satisfied. However, Hadamard’s Uniqueness condition will be satisfied, if A has full rank. In this case, Null Space(A) = {0}, i.e.,

 Ax+0=Ax=y. (5)

This linear system is called over-determined, because its equations, i.e., system constraints, are too many for x to exist [4, 5]. Also, the inverse of A does not exist.

### 2.3. Square linear systems

The case where m = n, the number of equations is equal to the number of unknowns,

 A=a11⋯a1n⋮⋱⋮an1⋯ann. (6)

If A has full rank, its Null Space(A) = {0} and both Hadamard’s Existence and Uniqueness conditions will be satisfied. In addition, if A has a small condition number, the relation between x, y will be continuous, and Hadamard’s Continuity condition will be satisfied [4, 5, 10]. In this case, the inverse problem formulated by this system of linear equations is well-posed.

## 3. Methods for signal estimation

In this section, we will focus on the estimation of an input signal x from a noisy measurement y of the output of a linear system A.

The linear system shown in Figure 1, could be modeled as,

 y=Ax+v. (7)

#### Figure 1.

Linear system with noisy output measurement.

where v is additive Gaussian noise. As a consequence of the Central Limit Theorem, this assumption of Gaussian distributed noise is valid for many output measurement setups.

Statistical Estimation Theory allows one to obtain an estimate x̂ of a signal x that is input to a known system A from measurement y (see Figure 2) [11, 12]. However, this estimate x̂ is not unique, as it depends on the choice of the used estimator from the different ones available. In addition to measurement y, if other information about the input signal is available, it could be used as prior information to constrain the estimator to produce a better estimate of x. Signal estimation for overdetermined systems could be achieved without any prior information about the input signal. However, for underdetermined systems, prior information is necessary to ensure a unique estimate.

#### Figure 2.

Signal estimation using prior information.

### 3.1. Least squares estimation

If there is no information available about the statistics of the measured data,

 y=Ax+v, (8)

least squares estimation could be used. The least squares estimate is obtained by minimizing the square of the L2 norm of the error between the measurement and the linear model, v = y − Ax. It is given by

 x̂=arg minx∥y-Ax∥22. (9)

The L2 norm is a special case of the p-norm of a vector, where p = 2, that is defined as xp=i=1mxip1p. In Eq. (9), the unknown x is considered deterministic, so its statistics are not required. The noise v in this formulation is implicitly assumed to be white noise with variance σ2 [13, 14]. Least squares estimation is typically used to estimate input signals x in overdetermined problems. Since x̂ is unique in this case, no prior information, additional constraints, for x is necessary.

### 3.2. Weighted least squares estimation

If the noise v in Eq. (8) is not necessarily white and its second order statistics, i.e., mean and covariance matrix, are known, then weighted least squares estimation could be used to further improve the least squares estimate. In this estimation method, measurement errors are not weighted equally, but a weighting matrix C explicitly specifies such the weights. The weighted least squares estimate is given by

 x̂=arg minx∥C-1/2y-Ax∥22. (10)

We note that the least squares problem, Eq. (9), is a special case of the weighted least squares problem, Eq. (10), when C = σ2I.

### 3.3. Regularized least squares estimation

In underdetermined problems, the introduction of additional constraints on x, also known as regularization, could ensure the uniqueness of the obtained solution. Standard least squares estimation could be extended, through regularization, to solve underdetermined estimation problems. The regularized least squares estimate is given by

 arg minx∥y-Ax∥22+λ∥Lx∥2, (11)

where L is a matrix specifying the additional constraints and λ is a regularization parameter whose value determines the relative weights of the two terms in the objective function. If the combined matrix AL has full rank, the regularized least squares estimate x̂ is unique [4]. In this optimization problem, the unknown x is once again considered deterministic, so its statistics are not required. It is worthwhile noting that while regularization is necessary to solve underdetermined inverse problems, it could also be used to improve numerical properties, e.g., condition number, of either linear overdetermined or linear square inverse problems.

### 3.4. Maximum likelihood estimation

If the probability distribution function (pdf) of the measurement y, parameterized by an unknown deterministic input signal x, is available, then the maximum likelihood estimate of x is given by,

 x̂=arg maxxfy|x. (12)

This maximum likelihood estimate x̂ is obtained by assuming that measurement y is the most likely measurement to occur given the input signal x. This corresponds to choosing the value of x for which the probability of the observed measurement y is maximized. In maximum likelihood estimation, the negative log of the likelihood function, f(y|x), is typically used to transform Eq. (12) into a simpler minimization problem. When, f(yx) is a Gaussian distribution, N(Ax, C), minimizing the negative log of the likelihood function is equivalent to solving the weighted least squares estimation problem.

### 3.5. Bayesian estimation

If the conditional pdf of the measurement y, given an unknown random input signal x, is known, in addition to the marginal pdf of x, representing prior information about x, is given, then a Bayesian estimation method would be possible. The first step to obtain one of the many possible Bayesian estimates of x is to use Bayes rule to obtain the a posteriori pdf,

 fxy=fy|x)fx∫fy|x)fx. (13)

Once this a posteriori pdf is known, different Bayesian estimates x̂ could be obtained. For example, the minimum mean square error estimate is given by,

 x̂MMSE=Exfxy=Exfy|x)fx∫fy|x)fx, (14)

while the maximum a priori (MAP) estimate is given by,

 x̂MAP=argmaxxfxy=argmaxxfy|x)fx. (15)

We note that the maximum likelihood estimate, Eq. (12), is a special case of the MAP estimate, when f(x) is a uniform pdf over the entire domain of x. The use of prior information is essential to solve underdetermined inverse problems, but it also improves the numerical properties, e.g., condition number, of either linear overdetermined or linear square inverse problems.

#### 3.5.1. Bayesian least squares estimation

In least squares estimation, the vector x is assumed to be an unknown deterministic variable. However, in Bayesian least squares estimation, it is considered a vector of scalar random variables that satisfies statistical properties given by an a priori probability distribution function [5]. In addition, in least squares estimation, the L2 norm of the measurement error is minimized, while in Bayesian least squares estimation, it is the estimation error, e=x̂-x, not measurement error, that is used [5]. Since x is assumed to be a random vector, the estimation error e will also be a random vector. Therefore, the Bayesian least squares estimate could be obtained by minimizing the condtional mean of the square of the estimation error, given measurement, y,

 x^=argminxE[(x^−x)T(x^−x)y]. (16)

When x has a Gaussian distribution and A represents a linear system, then measurement y will also have a Gaussian distribution. In this case, the Bayesian least squares estimate given by Eq. (16) could be reinterpreted as a regularized least squares estimate given by,

 x̂=argminx∥y-Ax∥22+∥μ-x∥, (17)

where μ is the mean of the a priori distribution of x [5]. Therefore, a least squares Bayesian estimate is analogous to a regularized least squares estimate, where a priori information about x is expressed as additional constraints on x in the form of a regularization term.

#### 3.5.2. Advantages of Bayesian estimation over other estimation methods

Bayesian estimation techniques could be used, given that a reliable a priori distribution is known, to obtain an accurate estimate of a signal x, even if the number available measurements is smaller than the dimension of the signal to estimated. In this underdetermined case, Bayesian estimation could accurately estimate a signal while un-regularized least squares estimation or maximum likelihood estimation could not. The use of prior information in Bayesian estimation could also improves the numerical properties, e.g., condition number, of either linear overdetermined or linear square inverse problems. This could be understood by keeping in mind the mathematical equivalence between obtaining one scalar measurement related to x, and specifying one constraint that x has to satisfy. Therefore, as the number of available measurements significantly increases, both Bayesian and maximum likelihood estimates would converge to the same estimate.

Bayesian estimation also could be easily adapted to estimate dynamic signals that change over time. This is achieved by sequentially using past estimates of a signal, e.g., xt − 1, as prior information to estimate its current value xt. More generally, Bayesian estimation could be easily adapted for data fusion, i.e., combination of multiple partial measurements to estimate a complete signal in remote sensing, stereo vision and tomographic imaging, e.g., Positron emission tomography (PET), Magnetic resonance imaging (MRI), computed tomography (CT) and optical coherence tomography (OCT). Bayesian methods could also easily fuse all available prior information to provide an estimate based on measurements, in addition to all known information about a signal.

Bayesian estimation techniques could be extended in straight forward ways to estimate output signals of nonlinear systems or signals that have complicated probability distributions. In these cases, numerical Bayesian estimates are typically obtained using Monte Carlo methods.

#### 3.5.3. Sparsity as prior information for underdetermined Bayesian signal estimation

Sparse signal representation means the representation of a signal in a domain where most of its coefficients are zero. Depending on the nature of the signal, one could find an appropriate domain where it would be sparse. This notion could be useful in signal estimation because assuming that the unknown signal x is sparse could be used as prior information to obtain an accurate estimate of it, even if only a small number of measurements are available. The rest of this chapter will focus on using signal sparsity as prior information for underdetermined Bayesian signal estimation.

## 4. Sparse signal representation

As shown in Figure 3, a sinusoid is a dense signal in the time domain. However, it could be represented by a single value, i.e., it has a sparse representation, in the frequency domain.

#### Figure 3.

A sinusoid in time and frequency domains.

We note that any signal could have a sparse representation in a suitable domain [15]. A sparse signal representation means a representation of the signal in a domain where most of its coefficients are zero. Sparse signal representations have many advantages including:

1. A sparse signal representation requires less memory for its storage. Therefore, it is a fundamental concept for signal compression.

2. A sparse signal representation could lead to simpler signal processing algorithms. For example, signal denoising could be achieved by simple thresholding operations in a domain where the signal is known to be sparse.

3. Sparse signal representations have fewer coefficients than dense signal representations. Therefore, the computational cost for sparse representations would be lower than for dense representations.

### 4.1. Signal representation using a dictionary

A dictionary D is a collection of vectors {φn}Γ, indexed by a parameter n ϵ Γ equal to the dimension of a signal f, where we could represent f as a linear combination [16],

 f=∑nϵΓcnφn. (18)

If the vectors {φn}Γ are linearly independent, then such dictionary is called a basis. Representing a signal as a linear combination of sinusoids, i.e., using a Fourier dictionary, is very common. Wavelet dictionaries and Chirplet dictionaries are also common dictionaries for signal representation. Dictionaries could be combined together to obtain a larger dictionary, where n ϵ Γ is larger than the dimension the signal f, that is called an overcomplete dictionary or a frame.

#### 4.1.1. Signal representation using a basis

A set of vectors form a basis for Rn if they span Rn and are linearly independent. A basis in a vector space V is a set X of linearly independent vectors such that every vector in V is a linear combination of elements in X. A vector space V is finite dimensional if it has a finite number of basis vectors [17].

Depending on the properties of {φn}Γ, bases could be classified into different types, e.g., orthogonal basis, orthonormal basis, biorthogonal basis, global basis and local basis. For an orthogonal basis, its basis vectors in the vector space V are mutually orthogonal,

 φmφn=0form≠n. (19)

For an orthonormal basis, its basis vectors in the vector space V are mutually orthogonal and have unit length,

 φmφn=δm-n, (20)

where δ(m − n) is the Kronecker delta function. For a biorthogonal basis, its basis vectors are not orthogonal to each other, but they are orthogonal to vectors in another basis, φ̃nnϵΓ, such that

 φmφ̃n=δm-n. (21)

In addition, depending on the domain (support) on which these basis vectors are defined, we could also classify a basis as either global or local. Sinusoidal basis vectors used for the discrete Fourier transform are defined on the entire domain (support) of f, so they are considered a global basis. Many wavelet basis vectors used for the discrete wavelet transform are defined on only part of the domain (support) of f, so they are considered a local basis.

#### 4.1.2. Signal representation using a frame

A frame is a set of vectors {φn}Γ that spans Rn and could be used to represent a signal f from the inner products {〈fφn〉}Γ. A frame allows the representation of a signal as a set of frame coefficients, and its reconstruction from these coefficients in a numerically stable way

 f=∑nϵΓfφnφn. (22)

Frame theory analyzes the completeness, stability, and redundancy of linear discrete signal representations [18]. A frame is not necessarily a basis, but it shares many properties with bases. The most important distinction between a frame and a basis is that the vectors that comprise a basis are linearly independent, while those comprising frame could be linearly dependent. Frames are also called overcomplete dictionaries. The redundancy in the representation of a signal using frames could be used to obtain sparse signal representations.

### 4.2. Sparse signal representation as a regularized least squares estimation problem

If designed to concentrate the energy of a signal in a small number of dimensions, an orthogonal basis would be the minimum-size dictionary that could yield a sparse representation of this signal [15]. However, finding an orthogonal basis that yields a highly sparse representation for a given signal is usually difficult or impractical. To allow more flexibility, the orthogonality constraint is usually dropped, and overcomplete dictionaries (frames) are usually used. This idea is well explained in the following quote by Stephane Mallat:

“In natural languages, a richer dictionary helps to build shorter and more precise sentences. Similarly, dictionaries of vectors that are larger than bases are needed to build sparse representations of complex signals. Sparse representations in redundant dictionaries can improve pattern recognition, compression, and noise reduction but also the resolution of new inverse problems. This includes super resolution, source separation, and compressed sensing” [15].

Thus representing a signal using a particular overcomplete dictionary has the following goals [16]

• Sparsity—this representation should be more sparse than other representations.

• Super resolution—the resolution of the signal when represented using this dictionary should be higher than when represented in any other dictionary.

• Speed—this representation should be computed in O(n) or O(n log(n)) time.

A simple way to obtain an overcomplete dictionary A is to use a union of basis Ai that would result in the following representation of a signal y,

 (y)=([A1][A2][A3][A4][A5])︸A(x)⇒y=Ax, (23)

where A is a n × m matrix representing the dictionary and x are the coefficients representing y in the domain defined by A. Since A represents an overcomplete dictionary, the number of its rows will be less than the number of its columns. Eq. (23) is a formulation of the signal representation problem as an underdetermined inverse problem.

To obtain a sparse solution for Eq. (23) one needs to find an m × 1 coefficient vector x̂, such that,

 x̂=argminxy-Ax22+λx0, (24)

where ‖x0 is the cardinality of vector x, i.e., its number of nonzero elements, and λ > 0 is a regularization parameter that quantifies the tradeoff between the signal representation error,y-Ax22, and its sparsity level, ‖x0 [19]. The cardinality of vector x is sometimes referred to as the L0 norm of x, even though ‖x0 is actually a pseudo norm that does not satisfy the requirements of a norm in Rm. This sparse signal representation problem, Eq. (24), has a form similar to the regularized least squares estimation problem, Eq. (11), that would be underdetermined in the case of an overcomplete dictionary. Because of the correspondence between regularized least squares estimation and Bayesian estimation, the problem of finding a sparse representation of a signal could be formulated as a Bayesian estimation problem.

## 5. Compressed sensing

Compressed sensing involves the estimation of a signal using a number of measurements that are significantly less than its dimension [20]. By assuming that the unknown signal is sparse in the domain where the measurements were acquired, one could use this sparsity constraint as prior information to obtain an accurate estimate of the signal from relatively few measurements.

Compressed sensing is closely related to signal compression that is routinely used for efficient storage or transmission of signals. Compressed sensing was inspired by this question: instead of the typical signal acquisition followed by signal compression, is there a way to acquire (sense) the compressed signal in the first place? If possible, it would significantly reduce the number of measurements and the computation cost [20]. In addition, this possibility would allow acquisition of signals that require extremely high, hence impractical, sampling rates [21]. As an affirmative answer to this question, compressed sensing was developed to combine signal compression with signal acquisition [20]. This is achieved by designing the measurement setup to acquire signals in the domain where the unknown signal is assumed to be sparse.

In compressed sensing, we consider the estimation of an input signal xRn from m linear measurements, where m ≪ n. As discussed above, this problem could be written as an underdetermined linear system,

 y=Ax, (25)

where yRm and ARm×n represent the measurements and measurement (sensing) matrix, respectively.

Assuming that the unknown signal x is s-sparse, i.e., x ∈ ∑s has only s nonzero elements, in the domain specified by the measurement (sensing) matrix A, and assuming that A satisfies the restricted isometry property (RIP) of order 2s, i.e., there exists a constant δ2s ∈ (0, 1) such that,

 1-δ2sz22≤Az22≤1+δ2sz22, (26)

for all z ∈ ∑2s, then x could be reconstructed from m ≥ s measurements by different optimization algorithms [20]. When the measurements y are noiseless, x could be exactly estimated from,

 minxx0subjecttoAx=y. (27)

However, when the measurements y are contaminated by noise,x could be obtained as the regularized least squares estimate,

 x̂=argminxAx-y22+λx0. (28)

This minimization problem could also be mathematically reformulated and solved as a Bayesian estimation problem.

## 6. Obtaining sparse solutions for signal representation and signal estimation problems

From Sections 4 and 5 we note that the problem of obtaining a sparse signal representation, Eq. (24) and the problem of sparse signal estimation in compressed sensing, Eq. (28), both have the same mathematical form [11, 22],

 x̂=argminxy-Ax22+λx0. (29)

In this section, we describe different approaches to solving this minimization problem. From Eq. (29), we note that the first term of its RHS, y-Ax22, represents either signal reconstruction error (sparse signal representation problem) or measurement fitting error (sparse signal estimation in compressed sensing problem), while the second term of its RHS,‖x0, represents the cardinality (number of nonzero coefficients) of the unknown signal. The regularization parameter λ specifies the tradeoff between these two terms in the objective function. The selection of an appropriate value of λ to balance the reconstruction, or fitting error, and signal sparsity is very important. Regularization theory and Bayesian approaches could provide ways to determine optimal values of λ [2326].

Convex optimization problems is a class of optimization problems that are significantly easier to solve compared to nonconvex problems [34]. Another advantage of convex optimization problems is that any local solution, e.g., a local minimum, is guaranteed to be a global solution. We note that obtaining an exact solution for the minimization problem in Eq. (29) is difficult because it is nonconvex. Therefore, one could either seek an approximate solution to this nonconvex problem or approximate this problem by a convex optimization whose exact solution could be obtained easily.

Considering the general regularized least squares estimation problem,

 x̂=argminxy-Ax22+λxp, (30)

we note that it is a nonconvex optimization problem for 0 ≤ p < 1 and a convex optimization problem for p ≥ 1. One alternative to approximate Eq. (29) by a convex optimization problem, one could relax the strict condition of minimizing the cardinality of the signal, ‖x0, by replacing by it by the sparsity-promoting condition of minimizing the L1 norm of the signal, ‖x1. Another alternative to approximate Eq. (29) by another nonconvex optimization problem that is easier to solve than the original problem using a Bayesian formulation, is to replace ‖x0 by ‖xp, 0 < p < 1. The minimization of Eq. (30) using ‖xp, 0 < p < 1 would result in a higher degree of signal sparsity compared to when ‖x1 is used. This could be understood visually by examining Figure 4, that shows the shapes of two-dimensional unit balls using (pseudo)norms with different values of p.

#### Figure 4.

Two-dimensional unit ball using different (pseudo)norms. (a) L0, (b) L0−1, and (c) L1.

We explain further details in the following subsections.

### 6.1. Obtaining a sparse signal solution using L0 minimization

The sparsest solution of the regularized least squares estimation problem, Eq. (29) would be obtained when p = 0 in ‖xp. As shown in Figure 5, the solution of the regularized least squares problem, x̂, is given by the intersection of the circles, possibly ellipses, representing the solution of the unconstrained least squares estimation problem and the unit ball using L0 representing the constraint of minimizing L0. In this case of minimizing L0, the unconstrained least squares solution will always intersect the unit ball at an axis, this yielding the most possible sparse solution. However, as mentioned earlier, this L0 minimization problem is difficult to solve because it is nonconvex. Approximate solutions for this problem could be obtained using greedy optimization algorithms, e.g., Matching Pursuits [27] and Least Angle Regression (LARS) [28].

### Figure 5.

Regularized least squares using L0.

### 6.2. Obtaining a sparse signal solution using L1 minimization

On relaxing the nonconvex regularized least squares using L0 minimization problem, by setting p = 1, we obtain the convex L1 minimization problem. As shown in Figure 4(c), the unit ball using the L1 norm covers a larger area than the unit ball using the L0 pseudo norm, shown in Figure 4(a). Therefore, as shown in Figure 6, the solution for the regularized least squares problem using the L1 minimization would be sparse, but it should not be expected to be as sparse as the L0 minimization problem.

### Figure 6.

Regularized least squares using L1.

This L1 minimization problem could be solved easily using various algorithms, e.g., Basis Pursuits [16], Method of frames (MOF) [29], Lasso [30, 31], and Best Basis Selection [32, 33]. A Bayesian formulation of this L1 minimization problem is also possible by assuming that the a priori probability distribution of x is Laplacian, x ~ e− |x|.

### 6.3. Obtaining a sparse signal solution using L0 − 1 minimization

As discussed above, solving the regularized least squares problem with L0 minimization should yield the sparsest signal solution. However, only approximate solutions are available for this difficult nonconvex problem. Alternatively, solving the regularized least squares problem with L1 minimization should yield an exact sparse solution that would be less sparse than in the L0 case, but it is considerably easier to obtain.

The regularized least squares problem could also be formulated as an L0 − 1 minimization problem. As ‖xp, 0 < p < 1,that we abbreviate as L0 − 1, is not an actual norm, this optimization problem would be nonconvex [34]. The advantage of using L0 − 1 minimization is that, as shown in Figure 4(b), compared to unit ball using the L1 norm, the unit ball using the L0 − 1 pseudo norm has a narrower area that is concentrated around the axes. Therefore, as shown in Figure 7, the L0 − 1 minimization problem should yield a sparser solution compared to the L1 minimization problem.

### Figure 7.

Regularized least squares using L0−1.

Another advantage of using L0 − 1 minimization is that this nonconvex optimization problem could be easily formulated as a Bayesian estimation problem that could be solved using Markov Chain Monte Carlo (MCMC) methods. As shown in Figure 8, the product of student-t probability distributions has a shape similar to the unit ball using the L0 − 1 pseudo norm, so student-t distributions could be used as a priori distributions to approximate the L0 − 1 pseudo norm.

### Figure 8.

Product of two student-t probability distributions.

### 6.4. Bayesian method to obtain a sparse signal solution using L0 − 1 minimization

As mentioned in Section 3.5, the first step to obtaining one of the many possible Bayesian estimates of x is to use Bayes rule to obtain the a posteriori pdf,

 fxy=fy|x)fx∫fy|x)fx. (31)

Using this a posteriori distribution, one could obtain a sparse signal solution using L0 − 1 minimization, as the maximum a posteriori (MAP) estimate given by Eq. (15). Compared to other Bayesian estimates, the MAP estimate could be easier to obtain because the calculation of the normalizing constant, ∫f(y|x)f(x),would not be needed. The maximization of the product of conditional probability distribution of y given x and the a priori distribution of x is equivalent to the minimizing of the sum of their negative logarithms,

 x̂MAP=arg minx-logpy|x-logpx. (32)

In the case of white Gaussian measurement noise, p(y|x) ~ Nx (Axσ2I) where -logpy|xy-Ax22, which the first term of the RHS of Eq. (30). As discussed in the previous section, the a priori probability p(x) corresponding to L0 − 1 minimization could be represented as a product of univariate student-t probability distribution functions [14],

 px=∏i=1Mstudxi01ϑ=∏i=1MΓϑ+12ϑπΓϑ21+xi2ϑ-ϑ+12, (33)

where Γ is the Gamma function, and ϑ is the number of degrees of freedom of the student-t distribution. Since this a priori distribution function is not an exponential function, we would use Eq. (15) instead of Eq. (32) to obtain the MAP estimate.

Because the prior is not a Gaussian distribution, there is no simple closed form expression for the posterior, p(x|y) with a student-t a priori probability distribution. However, we could express each student-t distribution as an infinite weighted sum of Gaussian distributions, where the hidden variables hi determine their variances [14].

 px=∏i=1M∫Nxi0,1/hiGamhiϑ/2,ϑ/2dhi=∫Nx0H-1∏i=1MGamhiϑ/2,ϑ/2dH, (34)

where the matrix H contains the hidden variables hii=1M on its diagonal and has zeros elsewhere, and Gamhiϑ/2,ϑ/2 is the gamma probability distribution function with parameters (ϑ/2, ϑ/2). Using this approximation, the a posteriori pdf could be written as

 px|y∝py|xpx=NxAx,σ2I∫Nx0H-1∏i=1MGamhiϑ2ϑ2dH=∫NxAx,σ2INx0H-1∏i=1MGamhiϑ2ϑ2dH. (35)

The product of two Gaussian distributions is also a Gaussian distribution [35],

 Nxμ1Σ1Nxμ2Σ2=k.NxμΣ, (36)

where the mean and covariance (μ, Σ) of the new Gaussian distribution in Eq. (36) is given by,

 μ=Σ1-1+Σ2-1-1Σ1-1μ1+Σ2-1μ2andΣ=Σ1-1+Σ2-1-1, (37)

and k is a constant. Therefore, we could simplify the product of two the Gaussian distributions given in Eq. (35) as,

 NxAx,σ2I.Nx0H-1=k.Nxσ-2I+H-1σ-2Ax,σ-2I+H-1. (38)

From Eqs. (35) and (38) we could write p(x|y) as,

 px|y=k∫Nxσ-2I+H-1σ-2Ax,σ-2I+H-1∏i=1MGamhiϑ2ϑ2dH. (39)

We still could not compute the integral in Eq. (39) in closed form. However, we could maximize the RHS of Eq. (39) over the hidden variables H to obtain an approximation for the a posteriori probability distribution function

 px|y≈arg maxHNxσ-2I+H-1σ-2Ax,σ-2I+H-1∏i=1MGamhiϑ2ϑ2. (40)

Eq. (40) would be a good approximation of p(x|y), if the actual distribution over the hidden variables is concentrated tightly around its mode [14]. When hi has a large value, its corresponding ith component of the a priori probability distribution function p(x) would have a small variance, 1hi, so that this ith component of p(x) could be set to zero. Therefore, this ith dimension of the prior p(x) would not contribute to the solution of Eq. (30), thus increasing its sparsity.

Since both Gaussian and gamma pdfs in Eq. (40) are members of the exponential family of probability distributions, we could obtain x̂MAP by maximizing the sum of their logarithms. Section 3.5 in [11] and Section 8.6 in [14] describe an iterative optimization method to obtain x̂MAP from the approximate a posteriori probability distribution function given by Eq. (40).

## 7. Conclusion

In this chapter, we described different methods to estimate an unknown signal from its linear measurements. We focused on the underdetermined case where the number of measurements is less than the dimension of the unknown signal. We introduced the concept of signal sparsity and described how it could be used as prior information for either regularized least squares or Bayesian signal estimation. We discussed compressed sensing and sparse signal representation as examples where these sparse signal estimation methods could be applied.

## References

1 - Keesman KJ. System Identification: An Introduction. London: Springer Science & Business Media; 2011
2 - Von Bertalanffy L. General system theory. New York. 1968;41973(1968):40
3 - Chen C-T. Linear System Theory and Design. New York, NY: Oxford University Press, Inc.; 1999
4 - Moon TK, Stirling WC. Mathematical Methods and Algorithms for Signal Processing. Upper Saddle River, NJ: Prentice Hall; 2000
5 - Fieguth P. Statistical Image Processing and Multidimensional Modeling. New York, NY: Springer Science+Business Media, LLC; 2011
6 - Tarantola A. Inverse problem theory and methods for model parameter estimation. Philadelphia, PA: Society for Industrial and Applied Mathematics; 2005. p. 1-37
7 - Ljung L. Perspectives on system identification. Annual Reviews in Control. 2010 Apr 30;34(1):1-2
8 - Wellstead PE. Non-parametric methods of system identification. Automatica. 1981 Jan 1;17(1):55-69
9 - Shanmugan KS, Breipohl AM. Random Signals: Detection, Estimation, and Data Analysis. New York, NY: Wiley; 1997
10 - Saad Y. Iterative Methods for Sparse Linear Systems. Philadelphia, PA: Society for Industrial and Applied Mathematics; 2003.
11 - Bishop CM. Pattern Recognition and Machine Learning. New York, NY: Springer; 2006
12 - Mendel JM. Lessons in Estimation Theory for Signal Processing, Communications, and Control. Englewood Cliffs, N.J.: Prentice-Hall; 1995
13 - Sorenson HW. Least-squares estimation: From Gauss to Kalman. IEEE Spectrum. 1970 Jul;7(7):63-68
14 - Prince SJ. Computer Vision: Models, Learning, and Inference. Cambridge: Cambridge University Press; 2012
15 - Mallat S. A Wavelet Tour of Signal Processing: The Sparse Way. Amsterdam: Academic Press; 2009
16 - Chen SS, Donoho DL, Saunders MA. Atomic decomposition by basis pursuit. SIAM Review. 2001;43(1):129-159
17 - Paul R. Halmos. Finite-Dimensional Vector Spaces. Mineola, UNITED STATES: Dover Publications; 2017
18 - Mallat S. A Wavelet Tour of Signal Processing. San Diego: Academic Press; 1999
19 - Shannon CE. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review. 2001;5(1):3-55
20 - Eldar YC, Kutyniok G, editors. Compressed Sensing: Theory and Applications. Cambridge: Cambridge University Press; 2012
21 - Asif MS. Dynamic compressive sensing: Sparse recovery algorithms for streaming signals and video [Doctoral dissertation]. Georgia Institute of Technology
22 - Huang K, Aviyente S. Sparse representation for signal classification. In: NIPS. Vol. 19; 2006. pp. 609-616
23 - Poggio T, Torre V, Koch C. Computational vision and regularization theory. Nature. 1985 Sep 26;317(6035):314-319
24 - Tikhonov AN, Arsenin VI. Solutions of Ill-posed Problems. Washington, DC: Winston; 1977 Jan
25 - Wahba G, Wendelberger J. Some new mathematical methods for variational objective analysis using splines and cross validation. Monthly Weather Review. 1980 Aug;108(8):1122-1143
26 - Lin Y, Lee DD. Bayesian L1-Norm Sparse Learning. In: 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings. Toulouse, France: vol. 5; 2006. p. V?V.
27 - Mallat SG, Zhang Z. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing. 1993 Dec;41(12):3397-3415
28 - Efron B, Hastie T, Johnstone I, Tibshirani R. Least angle regression. The Annals of Statistics. 2004 Apr;32(2):407-499
29 - Daubechies I. Time-frequency localization operators: A geometric phase space approach. IEEE Transactions on Information Theory. 1988 Jul;34(4):605-612
30 - Tibshirani R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological). 1996 Jan 1;58(1):267?288
31 - Yuan M, Lin Y. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 2006 Feb 1;68(1):49-67
32 - Coifman RR, Wickerhauser MV. Entropy-based algorithms for best basis selection. IEEE Transactions on Information Theory. 1992 Mar;38(2):713-718
33 - Rao BD, Kreutz-Delgado K. An affine scaling methodology for best basis selection. IEEE Transactions on Signal Processing. 1999 Jan;47(1):187-200
34 - Boyd S, Vandenberghe L. Convex Optimization. New York: Cambridge University Press; 2004.
35 - Bromiley P. Products and convolutions of Gaussian probability density functions. Tina-Vision Memo. 2003;3(4):1?13.


text:
### 9 PA-DIM Methods

AutoAdjustPositioner is a method used to initiate an automatic commissioning cycle of an actuator. The execution of the commissioning procedure can be started or aborted by calling the method using the appropriate input argument value. If the commissioning will not be aborted, it ends automatically after it has been finished. The commissioning procedure is manufacturer-specific.

Signature

AutoAdjustPositioner (
[in] ExecutionModeEnum ExecutionMode
);

Argument Description
ExecutionMode The desired execution mode, see 10.2 for a definition of all available values.


text:
Registered users can edit this wiki.

Laythe

 Laythe Laythe as seen from orbit. Moon of Jool Orbital Characteristics Semi-major axis 27 184 000 m [Note 1] Apoapsis 27 184 000 m [Note 1] Periapsis 27 184 000 m [Note 1] Orbital eccentricity 0 Orbital inclination 0 ° Argument of periapsis 0 ° Longitude of the ascending node 0 ° Mean anomaly 3.14 rad (at 0s UT) Sidereal orbital period 52 981 s 2 d 2 h 43 m 0.9 s Synodic orbital period 53007.7 s Orbital Velocity 3223.8 m/s Physical Characteristics Equatorial radius 500 000 m Surface area 3.1415927×1012 m2 Mass 2.9397663×1022 kg Standard gravitational parameter 1.9620000×1012 m3/s2 Density 56 145.401 kg/m3 Surface gravity 7.85 m/s2 (0.8 g) Escape velocity 2 801.43 m/s Sidereal rotation period 52 980.879 s 2 d 2 h 43 m 0.9 s Sidereal rotational velocity 59.297 m/s Synchronous orbit 4 686.32 km Sphere of influence 3 723 645.8 m[Note 1] Atmospheric Characteristics Atmosphere present ✓ Yes Atmospheric Pressure 81.0600 kPa 0.8 atm Scale height 4000 m Atmospheric height 55 262.042 m 8.0×10-7 atm Temperaturemin -40.19 °C 232.96 K Temperaturemax 6.21 °C 279.36 K Oxygen present ✓ Yes Scientific multiplier Surface 14 Lower atmosphere 11 Upper atmosphere 10 Near space 9 Outer space 8 The distances are given from the bodies center not surface (unlike ingame)

Laythe is the first of the five natural satellites of Jool. Although mostly covered in seas, Laythe has numerous rocky, sandy islands. Laythe is tidally locked to Jool. Synchronous orbits around Laythe are not possible, as they would lie outside of its SOI, at a radius of 5,186,399 meters. A circular archipelago prominent in surface maps of the moon suggests that Laythe suffered a massive impact in its distant past.

Achieving a stable orbit around Laythe from sea level requires a delta-V of ≈2800 m/s.

Laythe has no real-world analogue. In the real-world Jupiter system, the moons Ganymede, Europa and Io form a group with an orbital resonance just like KSP's Tylo, Vall and Laythe. But while Tylo and Vall have a certain resemblance to their real-life counterparts, Laythe is very unlike the volcanic, atmosphere-less, dry Io. Instead, the presence of a liquid ocean - plus a dense atmosphere - makes Laythe more similar to the Saturnian moon, Titan. Laythe also seems very similar to what happened to Europa in 2010: Odyssey Two.

Although Laythe has liquid water on its surface, the temperature there is below zero degrees Celsius. This means that Laythe's oceans must contain another compound, most likely ionic, such as salt. Surface samples indicate that much salt is present on Laythe's surface. Unlike that of Kerbin, the air cannot be breathed by Kerbals (according to EVA reports). It is therefore possible that there are also high concentrations of salt in the air, as well as on the surface, assuming that the salt is sodium chloride. The apparent toxicity of Laythe's atmosphere, despite being similar in composition to Kerbin's, may also be a reference to the film Avatar - the moon Pandora is very similar to Earth, but its atmosphere is too toxic for humans to inhale, and the moon also orbits a gas giant, like Laythe.

According to former developer NovaSilisko, Laythe was planned to have volcanic, probably cryovolcanic, activity and high radiation levels in later versions, making it a much more hostile moon than in 0.23.[1][2]

In-game Description

 “ When Laythe was first discovered, it was not entered in the records because the scientist in charge thought he was looking at Kerbin. Luckily this error was corrected when a plucky intern informed him that telescopes don’t work that way. The intern was shortly afterwards promoted and moved to the experimental rocket testing program.— Kerbal Astronomical Society ”

Biomes

Laythe has 4 biomes. Laythe exists of a huge ocean, called The Sagen Sea, with some small Dunes and Shores biomes. It also has a Poles biome. There is also a rumour of a biome called "Cresent Bay", but as of 0.90, until proven otherwise, it's not reachable.

Biome list

 Laythe biome map as of 0.90.0 Poles Shores Dunes The Sagen Sea

Atmosphere

Laythe's atmosphere begins at 55,262 meters and is 20% thinner than Kerbin's. It is the only moon in the game which has an atmosphere.

Like all other atmospheres in the game, Laythe's atmosphere fades exponentially with increasing altitude (with a scale height of 4000 m). In general, the atmospheric pressure on Laythe at an altitude expressed in meters is:[3]

$p_l = 0.8\ e^{-altitude/4000}$

With proper aerobraking near Laythe and Jool, reaching Laythe may require the least delta-V of all of Jool's moons. When approaching Jool on a Hohmann transfer orbit from Kerbin, aerobraking with a Jool periapsis of 119.5 km will put your apoapsis roughly near Laythe's orbit.

Another way is to approach Laythe directly, utilizing proper timing and making orbital adjustments on the way to Jool. Laythe's orbital period makes it an easy target to time and will have required less delta-v on arrival (only 2000 m/s). As such, aerobraking on Laythe is less extreme than on Jool.

Landing on higher points of Laythe's surface has to be done with the help of retro-burns, as parachutes alone will not suffice to sufficiently lower a craft's velocity for landing.

Jet engines work in Laythe's atmosphere due to the presence of oxygen. However, the air-intake efficiency is lower there.

Most of Laythe's surface is ocean. There are many craters on its surface, and some of the largest features it has may be related to impacts. Other features on the surface, such as small canyons, may have been carved out by flowing water that either came up through the surface or fell as rain when the planet was warmer.

Science

Laythe is the most science-rich body in the Joolean moon system. Even though Tylo has a slightly higher science multiplier for both surface and orbit, Laythe's atmosphere and oceans allow a lot more experiments to be performed, which means the total science output is higher.

Reference Frames

 Rotational/Inertial transition Warp 0 m 1× Any 5× 30 000 m 10× 30 000 m 50× 60 000 m 100× 120 000 m 1 000× 240 000 m 10 000× 480 000 m 100 000× 600 000 m

0.90


text:
# $\bar{S}(x,r)$, does not contain all y with $\rho(x,y)\leq r$

I am reading Rudin's Real and complex analysis, he mentioned there exist situations in which $\bar{S}(x,r)$, does not contain all y with $\rho(x,y)\leq r$, $S(x,r)$ is the open ball of $x$. Could someone help to explain it?

-

Let $X = [-1, 1] \cup \{-2, 2\}$ with the Euclidean distance. $\overline{S}(0, 2)$ doesn't contain $\{-2, 2\}$.
Or $\mathbb{N}$ with the Euclidean distance. –  copper.hat Nov 13 '12 at 0:38


text:
# Simple task... that drives me crazy (SDL_ttf)

This topic is 3991 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've just finished a tetris game, just one litle thing left; showing the current score for the player. I try to do this with:
sprintf(score_str, "Score: %ld", score);
text_surface = TTF_RenderText_Solid(font, score_str, (SDL_Color) {255, 255, 255});

text_surface gets the vale NULL! What am I doing wrong? When I print score_str with printf() everything looks like it should. Thanks in advance.

##### Share on other sites
Use TTF_GetError() to tell you why.

##### Share on other sites
Quote:
 Original post by rip-offUse TTF_GetError() to tell you why.

OK. Then I get "SDL_UpperBlit: passed a NULL surface". And what does that mean. :S

##### Share on other sites
Quote:
Quote:
 Original post by rip-offUse TTF_GetError() to tell you why.

OK. Then I get "SDL_UpperBlit: passed a NULL surface". And what does that mean. :S

SDL_BlitSurface is actually 2 functions inside SDL, UpperBlit and LowerBlit. AFAIK, lower blit does the raw transfer and upper blit performs checks on two surfaces and the rectangles to blit to/from. So SDL_UpperBlit was performing these checks and failed because one of the surfaces was NULL.

However, inspecting the SDL_ttf source code I can't find any calls to SDL_BlitSurface, SDL_UpperBlit or SDL_LowerBlit. This means that the error is coming from your own code.

Try the following, if you haven't already:

0) check the return value of TTF_Init(), printing TTF_GetError() if its below zero
1) check the font pointer returned by TTF_OpenFont(), and print TTF_GetError() if NULL
2) put some checks just before calling SDL_BlitSurface(), somewhere in your code you are blitting a NULL surface...

##### Share on other sites
Hmm... It seams like TTF_RenderText_Solid() doesn't like spaces, because when I changed the sprintf() call to sprintf(score_str, "Score:%ld", score); it worked! I just removed the space and it work. That's weird. :P

##### Share on other sites
Quote:
 Original post by Adam4444Hmm... It seams like TTF_RenderText_Solid() doesn't like spaces, because when I changed the sprintf() call to sprintf(score_str, "Score:%ld", score); it worked! I just removed the space and it work. That's weird. :P

I use SDL_ttf with spaces in the strings... its odd that it doesn't work.

##### Share on other sites
Why do I have a feeling 'score_str' doesn't have enough memory allocated, and ends up overrunning something?

##### Share on other sites
Quote:
 Original post by RepliconWhy do I have a feeling 'score_str' doesn't have enough memory allocated, and ends up overrunning something?

Yepp, of course there wasn't enough space. :P Silly error of me. Anyways, thanks for your time.

EDIT: I don't think so after all...

Here's the whole code for the function:
void draw_sidebar(void){    int i, j;    SDL_Surface *text_surface;    SDL_Rect src_rect, dest_rect;    SDL_Color text_color;    char score_buf[20];        SDL_FillRect(display_surface, &(SDL_Rect) {WIDTH * BLOCK_SIZE, 0, SIDEBAR_WIDTH, SIDEBAR_HEIGHT}, SDL_MapRGB(display_surface->format, 0, 0, 0));        text_color.r = text_color.g = text_color.b = 255;    /* Show the next figure. */    for (i = 0; i < 4; i++) {        for (j = 0; j < 4; j++) {            if (next_figure.pattern[j] != NOTHING) {                src_rect.x = src_rect.y = 0;                src_rect.w = src_rect.h = BLOCK_SIZE;                dest_rect.x = (j * BLOCK_SIZE) + (WIDTH * BLOCK_SIZE);                dest_rect.y = (i * BLOCK_SIZE) + 20;                dest_rect.w = dest_rect.h = BLOCK_SIZE;                SDL_BlitSurface(blocks[next_figure.pattern[j]], &src_rect, display_surface, &dest_rect);            }        }    }        /* Generate the text "Next:" over the next figure. */    text_surface = TTF_RenderText_Solid(font, "Next:", text_color);    src_rect.x = src_rect.y = 0;    src_rect.w = dest_rect.w = text_surface->w;    src_rect.h = dest_rect.h = text_surface->h;    dest_rect.x = WIDTH * BLOCK_SIZE + 8;    dest_rect.y = 2;    SDL_BlitSurface(text_surface, &src_rect, display_surface, &dest_rect);        /* View the score, level, and rows deleted. */    sprintf(score_buf, "Score: %lu", score);    text_surface = TTF_RenderText_Solid(font, score_buf, text_color);    src_rect.x = src_rect.y = 0;    src_rect.w = dest_rect.w = text_surface->w;    src_rect.h = dest_rect.h = text_surface->h;    dest_rect.y = 120;    SDL_BlitSurface(text_surface, &src_rect, display_surface, &dest_rect);            /* Draw the separation line, which seperate the sidebar from the game. */    boxRGBA(display_surface, (WIDTH * BLOCK_SIZE), 0, (WIDTH * BLOCK_SIZE) + 2, HEIGHT * BLOCK_SIZE, 200, 200, 200, 255);    SDL_UpdateRect(display_surface, 0, 0, 0, 0);    SDL_FreeSurface(text_surface);}

##### Share on other sites
Put score_buf 128 characters instead of 20, not the ~100 extra bytes that will kill your requiered specs and you will be safe if the player has a very high score...

##### Share on other sites
This sounds like a problem I was having for quite a long time. It turns out that there was a bug in freetype for a while that caused sdl_ttf to fail rendering strings with spaces. If this works when you remove the space then that's probably what you're running into.

The Gentoo bug regarding this problem is here: http://bugs.gentoo.org/show_bug.cgi?id=139494

It covers the details pretty well, and I assume this affected other platforms the same too.

##### Share on other sites
Quote:
 Original post by nemebeanThis sounds like a problem I was having for quite a long time. It turns out that there was a bug in freetype for a while that caused sdl_ttf to fail rendering strings with spaces. If this works when you remove the space then that's probably what you're running into.The Gentoo bug regarding this problem is here: http://bugs.gentoo.org/show_bug.cgi?id=139494It covers the details pretty well, and I assume this affected other platforms the same too.

Aha, thanks fot that information. But I think I skip the space, it gives the game a kind of hardcore feeling; http://www.burnie.nu/files/atetris_screenshot.png .
But it's good to know when I develop my next game. :)

##### Share on other sites
You have in your code this line:
SDL_BlitSurface(text_surface, &src_rect, display_surface, &dest_rect);
Change '&src_rect' to NULL and it should work. I may be mistaken, but by doing this:
src_rect.w = dest_rect.w = text_surface->w;src_rect.h = dest_rect.h = text_surface->h;
I would think your surface wouldn't show on-screen at all.(It looks like you are telling it to draw a non-existent portion of the texture) Are you sure text_surface is returning NULL, or are you assuming so, because it's not working? Ofcourse, this wouldn't explain why 'Next:' works, or why the score works without the space...

What exactly is happening? Is the text showing up on-screen? Partially on-screen? Nothing showing up? Is text_surface actually returing NULL? Is the text 'Next:' working fine?

[Edit:] NM, seems it's been solved.


text:
# Prove that the roots of unity is a cyclic group

## Homework Statement

Let ##\mu=\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1 \text{ for some integer }n \geq 1\}##. Show that ##\mu = \langle z \rangle## for some ##z \in \mu##.

## The Attempt at a Solution

My thought would be just to write out all of the elements of ##\mu## in exponential form and show that ##e^{\frac{2 \pi i}{n}}## generates all of the other elements. Would this be the best way to do this?

Delta2

member 587159

## Homework Statement

Let ##\mu=\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1 \text{ for some integer }n \geq 1\}##. Show that ##\mu = \langle z \rangle## for some ##z \in \mu##.

## The Attempt at a Solution

My thought would be just to write out all of the elements of ##\mu## in exponential form and show that ##e^{\frac{2 \pi i}{n}}## generates all of the other elements. Would this be the best way to do this?

Yes.

Delta2
andrewkirk
Homework Helper
Gold Member
The claim is actually false as given. The usual interpretation of
$$\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1 \text{ for some integer }n \geq 1\}$$
is
$$\{z\in \mathbb{C} \setminus \{0\} \mid \exists n\in \mathbb N \smallsetminus \{0\}\ :\ z^n = 1\}$$
which is
$$\{e^{\frac{2\pi k i }n} \mid n,k\in \mathbb Z \wedge 0\le k < n\}$$
which I am pretty sure is not cyclic, as the group generated by ##e^{\frac{2 \pi k i}n}## does not contain ##e^{\frac{2 \pi i}{2n}}##.

I suspect what they meant to say was :

"For each ##n\in \mathbb N\smallsetminus \{0\}##, define ##\mu_n =
\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1\}##. Show that for every ##n##, ##\mu_n## is cyclic."

To prove the second one, you don't need to write out all the elements. Instead, just show that all elements are of the form
##e^{\frac{2\pi k i }n}## where ##0\le k < n##. Then show that each of those elements can be expressed as a power of ##e^{\frac{2\pi i }n}##.

Delta2
The claim is actually false as given. The usual interpretation of
$$\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1 \text{ for some integer }n \geq 1\}$$
is
$$\{z\in \mathbb{C} \setminus \{0\} \mid \exists n\in \mathbb N \smallsetminus \{0\}\ :\ z^n = 1\}$$
which is
$$\{e^{\frac{2\pi k i }n} \mid n,k\in \mathbb Z \wedge 0\le k < n\}$$
which I am pretty sure is not cyclic, as the group generated by ##e^{\frac{2 \pi k i}n}## does not contain ##e^{\frac{2 \pi i}{2n}}##.

I suspect what they meant to say was :

"For each ##n\in \mathbb N\smallsetminus \{0\}##, define ##\mu_n =
\{z\in \mathbb{C} \setminus \{0\} \mid z^n = 1\}##. Show that for every ##n##, ##\mu_n## is cyclic."

To prove the second one, you don't need to write out all the elements. Instead, just show that all elements are of the form
##e^{\frac{2\pi k i }n}## where ##0\le k < n##. Then show that each of those elements can be expressed as a power of ##e^{\frac{2\pi i }n}##.
Your interpretation of the problem is correct. It is not a cyclic group. Actually what I need to show is this:
Prove that for each integer ##m \geq 1##, there is a unique subgroup ##H_m\leq \mu## with ##|H_m|=m## and that ##H_m## is cyclic.

It seems rather easy to show there exists one. Let ##\mu_m =\{z\in \mathbb{C} \setminus \{0\} \mid z^m = 1\}##. We can easily show that this is a cyclic subgroup of order ##m##. My problem is with the uniqueness requirement. What does it mean to show that ##\mu_m## is unique?

andrewkirk
Homework Helper
Gold Member
You have to show that if ##H_m## is a subgroup of order m then ##H_m=\mu_m##.

Start by showing that any ##g\in H_m## must satisfy ##g^m=1##.

You have to show that if ##H_m## is a subgroup of order m then ##H_m=\mu_m##.

Start by showing that any ##g\in H_m## must satisfy ##g^m=1##.
Well, since ##|H_m|=m##, if ##g \in H_m## then ##g^m=1## since m is a multiple of the order of ##g##. So ##g \in \mu_m##. Does this show that ##H_m \subseteq \mu_m##? And since ##|H_m|=m=\mu_m##, we have ##H_m = \mu_m##?

andrewkirk
Homework Helper
Gold Member
Yes, that is correct.

Mr Davis 97
Yes, that is correct.
I think I have only one more question. I want to show that if ##H \le \mu## is finitely generated, then ##H## is finite. Here is my idea. Let ##H## be an arbitrary subgroup of ##\mu## that is finitely generated. So ##H=\langle z_1,z_2, \dots, z_k\rangle##. We can only multiply elements in the generating set and powers of those elements in a finite number of ways, since each ##z## in the generating set has a finite order. But whenever we multiply any combination of elements, we get another element of finite order. Hence the size of ##H## is finite.

andrewkirk
Homework Helper
Gold Member
We can only multiply elements in the generating set and powers of those elements in a finite number of ways, since each ##z## in the generating set has a finite order.
This is correct, but a little vague, and doesn't lead directly to the result.

To put it more compactly, we can observe that, since the group is abelian and each generator has finite order, every element of $H$ can be expressed as
$$\prod_{j=1}^k z_j^{r_j}$$
for some ##k##-tuple ##r_1,....,r_k## such that ##\forall j:\ 0\le r_j <O_j##, where ##O_j## is the order of ##z_j##.
Then an upper bound for the number of elements is
$$\prod_{j=1}^k O_j$$

Mr Davis 97
This is correct, but a little vague, and doesn't lead directly to the result.

To put it more compactly, we can observe that, since the group is abelian and each generator has finite order, every element of $H$ can be expressed as
$$\prod_{j=1}^k z_j^{r_j}$$
for some ##k##-tuple ##r_1,....,r_k## such that ##\forall j:\ 0\le r_j <O_j##, where ##O_j## is the order of ##z_j##.
Then an upper bound for the number of elements is
$$\prod_{j=1}^k O_j$$
Would this same argument show that ##\mu## is not finitely generated? For suppose it were. Then by the same argument there is an upper bound for the number of elements, so it is finite. But ##\mu## is not finite, since there are infinitely many elements in ##\mu##. since ##\forall n \in \mathbb{N}##, ##e^{\frac{2 \pi}{n}i} \in \mu##.

andrewkirk


text:
Generate a file with SNPs given a WGS dataset
1
0
Entering edit mode
29 days ago
iibrams07 • 0

Given whole genome sequencing or whole-exome sequencing datasets of the human genome, I need to generate a list of all the SNPs present in each of the datasets separately. In the best scenario the SNPs should be well annotated, as for their genes they belong to, their coordinates, and eventually additional attributes. The file should have a .csv format or some other similar format, since I need to upload it and manipulate some data from it.

How should I proceed?

Many thanks.

annotation snp ngs • 538 views
1
Entering edit mode
29 days ago
Dave Carlson ▴ 620

There are a lot of ways to accomplish this general workflow, but my suggestion would be something along the following lines:

1. Map reads to the human reference genome with BWA MEM
2. Produce a bam file for each sample after sorting by position with samtools
3. Mark duplicates with Picard
4. Jointly call variants for all samples with GATK, following their best practices pipeline.
5. Annotate the variants using GATK's Funcotator, SnpEff, or Annovar
6. Depending on what specifically you want to do next, process the annotated VCF using vcftools, bcftools, or maybe PLINK to get additional information
0
Entering edit mode

@Dave Carlson. Many thanks. Once at step 6., what should I do to collect only the SNPs and discard other variants? I need to pipe this collection to maybe a text file. In the best practice pipeline, you are referring to, there is no SNP-based pipeline regarding the somatic case, it rather refers to germline SNPs. Do you know of a resource that provides the command line code to proceed step by step in achieving this goal?

1
Entering edit mode

To exclude all but SNPs from your VCF file you can use GATK's SelecVariants tool with --select-type-to-include SNP or bcftools with --skip-variants indels.

From the rest of your comment, it sounds like you're doing somatic variant calling. Is that right? If so, GATK has a separate best practices workflow for this, though I don't have any personal experience with it.

0
Entering edit mode

The samples the DNA was extracted from were somatic cells. It is surprising that GATK provides more pipelines for germ cells than somatic ones. The last best practice workflow you are referring to is not clearly telling if it is about SNPs. SNV is not the same as SNPs. It is totally different. Thus I am confused. Can you comment on this? I got another question. When I open the Github extracted code file, I find a .jason and .wdl file. What should I do with these files? What I need is the code. Is the code inside one of these files? How can I read them? Thanks.

0
Entering edit mode

SNP = single nucleotide polymorphism

SNV = single nucleotide variant

These two things are subtlety different, but they are not totally different.

I'm not sure which precise github page you're looking at, but if you're referring to the code for GATK, it's written in JAVA, and the easiest way to run it would be to download the latest release and call the wrapper script gatk.

0
Entering edit mode

By code I mean the command line code needed to run the pipeline and not to download GATK. Clicking at best practices workflow, one is led to a page of pipelines which are themselves linked to github pages where a code file is situated.