Data-Adaptive Inference
for Structural Sparsity

1. What TLasso is trying to solve

The target is not ordinary sparsity of $\beta$, but structural sparsity of

The generalized Lasso formulation is

The difficulty is that $\gamma$ is not always a free $m$-dimensional vector. If $\operatorname{rank}(D)=r<m$, then all feasible $\gamma$'s lie in a lower-dimensional subspace.

2. Row-space decomposition when D is usable

Using the Moore-Penrose inverse, decompose $\beta$ into the part visible to $D$ and the nuisance part invisible to $D$:

Plugging this into the regression model gives

Now $\gamma$ is the target and $\theta_2$ is nuisance.

3. Projection removes nuisance directions

Let $P_{XD^*}$ be the projection onto the column space of $XD^*$. Define

Multiply the model by $M$:

Since $M XD^*=0$, the nuisance part disappears:

Then solve a standard Lasso in $\gamma$:

4. Why lifting / noise injection is needed

If $D$ is rank-deficient or $m>p$, the direct decomposition may not give a free $m$-dimensional $\gamma$. TLasso augments the transformation by adding directions that span the missing row-rank part:

Correspondingly, augment the coefficient and design:

The auxiliary noise design $X_N$ supplies the extra directions needed for the lifted model. These directions are not scientific signals; they are introduced so the transformed target can be handled like a full-row-rank Lasso target.

5. Final lifted TLasso problem

After lifting, the working problem is

Then the same decomposition-and-projection logic applies to $D_+$ and $X_+$. After projecting out nuisance directions, TLasso again reduces to

• Lift: make the transformation full row rank.
• Project: remove nuisance directions.
• Lasso: select sparse transformed signals $\gamma_j$.

1. Why introduce $X_N$?

If $\operatorname{rank}(D)=r<m$, then $\gamma=D\beta$ is constrained to a lower-dimensional subspace. TLasso lifts the transformation by adding $m-r$ artificial directions:

To match these artificial directions in the regression design, we add an auxiliary noise matrix

2. The true coefficient of $X_N$ is zero

Write the lifted coefficient as

The auxiliary variables are not scientific signals. Their population coefficient is set to zero:

The transformed target is also unchanged:

So $X_N$ expands the computational formulation without changing the original regression signal or the original structural target.

3. The theoretical condition

The main requirement is that $X_N$ should be noise with respect to the response after conditioning on the original design:

Each auxiliary column should also add a genuinely new direction, so it should not be expressible as a deterministic function of $X$ and the other auxiliary columns.

4. Practical generation mechanisms

The paper suggests several ways to generate an initial $X_N^{(0)}$:

• Independent pseudo-variables: generate each $X_{N,j}$ independently of $(Y,X)$, for example Gaussian or other random noise columns.
• Flip-coin variables: generate Rademacher-type entries $X_{N,j}=\pm c_j$ with probability $1/2$ for a fixed scale $c_j>0$.
• Permuted original columns: randomly choose $m-r$ columns from $X$ and independently permute their rows, preserving marginal shape while breaking their alignment with $Y$.
• Orthogonalized version: after any of the above, project the initial noise away from the column space of $X$ when a nontrivial orthogonal complement is available.

5. Optional projection away from $X$

When $\operatorname{Col}(X)^\perp$ is nontrivial, use

This makes the auxiliary variables orthogonal to the original design:

In the simulations, the three TLasso variants correspond to the first three initial noise choices, followed by this projection step. Their similar performance is used as evidence that TLasso is not very sensitive to the exact noise-generation mechanism.

6. Why SATLasso later penalizes $\beta_N$

In moderate dimensions, random auxiliary noise is usually manageable. In ultra-high dimensions, however, $m-r$ can be large, so some columns of $X_N$ may have spurious sample correlation with $Y$.

SATLasso controls this by adding an $\ell_2$ penalty on the artificial coefficients:

This shrinks the auxiliary-noise component while still allowing TLasso to use the lifted geometry.

1. Why SATLasso is needed

StatKnock needs a manageable candidate set of transformed features. When the transformation dimension $m$ is ultra-high, directly testing all $\gamma_j=(D\beta)_j$ is computationally and statistically difficult.

SATLasso is a screening step in $\gamma$-space: it aims to keep all true transformed signals while reducing $m$ to a size where StatKnock can be applied.

2. Adjust TLasso to control injected noise

TLasso introduces auxiliary noise variables through $X_N$ and $\omega_N$. In ultra-high dimensions, too many noise variables can create spurious correlations with $Y$.

SATLasso first forms an adjusted TLasso, abbreviated ATLasso, by penalizing the noise coefficients:

• $\alpha=0$: reduces to the TLasso lifted problem.
• Large $\alpha$: forces $\omega_N$ closer to zero, moving back toward the original GLasso constraint.
• Adaptive $\alpha$: balances useful lifting against noise-induced bias.

3. Convert ATLasso to projected regression

The $\ell_2$ penalty can be written as an augmented regression problem:

Then the same TLasso projection idea gives a regression in the transformed coefficients:

At this point, SATLasso has a Lasso-like objective in $\gamma$, but it will solve it sequentially rather than globally all at once.

4. Sequential partial $\ell_1$ screening

SATLasso builds a selected set $S_k$ step by step. At the beginning, it penalizes all $\gamma_j$ and chooses the largest $\lambda_1$ that makes at least one coefficient nonzero.

After a set $S_k$ has been selected, the next step penalizes only the remaining candidates:

Previously selected coordinates are adjusted for, while unselected coordinates compete to enter next. This is why SATLasso captures joint effects better than marginal screening.

5. Stop by GBIC and update efficiently

After each step, SATLasso computes a generalized BIC for the current selected set:

The last term penalizes the huge model space. The algorithm stops when adding new variables increases GBIC:

To avoid repeated matrix inversion, the residual projector $W_{S_k}$ is updated recursively using the Sherman-Morrison formula.

6. What goes into post-screening FDR

The output is a screened transformation set $\widehat S_\gamma$. Under the sure-screening condition, it contains the true transformed active set with high probability:

Then StatKnock is applied on this reduced set. The important point is that the final inference still respects the original structural relationship $\gamma=D\beta$; the selected rows of $D$ are recycled back into the original $\beta$-space model.

1. What object is being constructed?

StatKnock does not construct knockoffs for the raw covariate matrix $X$ directly. It first uses TLasso to obtain a projected design for the transformed target $\gamma$.

Here $X^\downarrow$ is the TLasso-projected design. The knockoff matrix $\widetilde X$ is a synthetic copy of $X^\downarrow$ with one knockoff column for each transformed feature $\gamma_j$.

2. The two Gram-matrix requirements

After normalizing the columns of $X^\downarrow$, define its Gram matrix

The knockoff copy $\widetilde X$ is constructed to satisfy

• The first equation says the knockoff variables have the same dependence structure as the projected original variables.
• The second equation controls how correlated each original variable is with its knockoff counterpart.
• The vector $s=(s_1,\ldots,s_m)^T$ controls the original-knockoff separation: larger $s_j$ usually means more power, subject to feasibility.

3. Closed-form construction when enough samples are available

When $n\ge 2m$, one standard construction is

The matrix $\widetilde U\in\mathbb{R}^{n\times m}$ has orthonormal columns and is orthogonal to $\operatorname{Col}(X^\downarrow)$. The matrix $C$ is a Cholesky factor of

4. How the vector s is chosen

The vector $s$ cannot be arbitrary. It must keep the joint Gram matrix positive semidefinite:

In practice, $s$ is often chosen by a semidefinite program that tries to make the knockoffs as different from the originals as possible while satisfying the feasibility constraint.

5. Why this enables knockoff FDR control

The construction makes the joint design $[X^\downarrow,\widetilde X]$ invariant, in Gram-matrix form, when a null original column and its knockoff are swapped.

That exchangeability gives the sign-flip property for knockoff statistics $W_j$: under a null, the original and knockoff should be equally likely to win. The final threshold estimates how many discoveries are likely false by counting knockoff wins.

1. Regression model

The simulation uses the standard high-dimensional linear model

The rows of $X$ are generated independently from a correlated Gaussian design:

For the FDR/power figure on this slide, the correlation parameter is $\rho=0.2$ and the target FDR level is $q=0.2$.

2. Structural signal being tested

The scientific target is not whether individual $\beta_j$'s are nonzero. The target is whether transformed coefficients are nonzero:

For this slide, $D=\Delta_{G_1}^{(1)}$ is the first-order graph difference operator on a chain graph, so nonzero $\gamma_j$ means a local jump between neighboring vertices.

3. Signal size and sparsity settings

The figure varies the density of the original coefficient vector $\beta$ while keeping the structural signal sparse.

This is exactly the setting where methods that screen in $\beta$-space can lose power: $\beta$ may be dense even when $\gamma$ is sparse.

4. Dimensions and procedures

The simulation studies two ultra-high transformation dimensions:

StatKnock uses $L=100$ subsamples. The competitors are chosen as high-dimensional versions of existing FDR methods for structural sparsity:

• BY: compute p-values for each transformed coordinate and apply Benjamini-Yekutieli correction.
• GKnockoff: use FuSIS screening followed by generalized knockoffs.
• SplitKnockoff: use Lasso screening, SplitLasso, then SplitKnockoff.

5. Why this model favors the proposed workflow

The key stress test is the gap between sparse structural signal and potentially dense original coefficients:

SATLasso screens directly in $\gamma$-space, so it is designed to keep the true structural jumps. BY, GKnockoff, and SplitKnockoff can become conservative because their screening or p-value construction is less aligned with the transformed target.